Longest Common Prefix

Problem: Write a function to find the longest common prefix string amongst an array of strings.

 


public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0 || strs[0] == null || strs[0].length() == 0) return "";
        
        StringBuilder sb = new StringBuilder();
        
        int shortestLen = strs[0].length();
        
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() == 0) return "";
            if (strs[i].length() < shortestLen) shortestLen = strs[i].length();
        }
        
        for (int i = 0; i < shortestLen; i++) {
            boolean flag = true;
            char current = strs[0].charAt(i);
            for (int j = 0; j < strs.length; j++) {
                if (strs[j].charAt(i) != current) {
                    flag = false;
                    break;
                }
            }
            if (!flag){
                break;
            }
            sb.append(current);
            
        }
        
        return sb.toString();
        
    }
}

Advertisements

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