find longest common prefix

package algorithm.weixin;

public class LargestCommonPrefix {
    /**
     *    find largest common prefix
     *
     *    assume all string are not null and not blank
     *
     **/
    public static String findLCP( String[] arr )
    {
        int i = 0;
        int j;
        int endPos = 0;
        while( i < arr[0].length() )
        {
            // compare arr[0].charAt(i) with all ith elements in other string
            for( j = 1; j < arr.length; j++ )
            {
                // if find non-equal, terminate immediately and return the last time match
                if( i < arr[j].length() && arr[j].charAt( i ) != arr[0].charAt( i ) )
                {
                    endPos = i -1;
                    return arr[0].substring(0, endPos+1);
                }
            }
            // if compare complete, then we can move forward
            if( j == arr.length )
            {
                i++;
            }
        }
        return null;
    }
    public static void main( String[] args )
    {
        String[] arr = {"abcde", "abcefg", "abcefss", "abefaafddfa"};
        System.out.println( findLCP( arr ) );
    }

}

Advertisements
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s