Wednesday, January 7, 2015

LeetCode 14: Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        // Firstly find the minmimum length of strings
        // Then from left to right, check one by one
        String str = "";
        int n = strs.length; // Number of strings
        
        if (n == 0)
            return str;
            
        if (n == 1)
            return strs[0];
            
        int minLen = strs[0].length(); // Minimum length of strings
        
        for (int i = 1; i < n; i++)
            minLen = Math.min(minLen, strs[i].length());
            
        for (int i = 0; i < minLen; i++)
        {
            char c = strs[0].charAt(i);
            
            for (int j = 1; j < n; j++)
                if (c != strs[j].charAt(i))
                    return str;
            
            str += String.valueOf(c);
        }
        
        return str;
    }
}

No comments:

Post a Comment