Wednesday, November 7, 2012

[Leetcode] Longest common prefix

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

解题思路:
1. 遍历数组,找出当前commonprefix下一个str的commonprefix。
2. 查看数组里所有的变量的第i位置上的字符相等否
   public String longestCommonPrefix(String[] strs) {
        String prefix = "";
        
        if(strs.length == 0) return prefix;
        
        prefix = strs[0];
        
        for(int i = 1; i < strs.length && prefix.length() > 0; i++){
            
            int j = 0;
            
            while(j < prefix.length() && j < strs[i].length() && prefix.charAt(j) == strs[i].charAt(j)) j++;
            
            prefix = prefix.substring(0, j);
        }
        
        return prefix;
    }





public String longestCommonPrefix(String[] strs) {
         String res = "";
        if(strs.length == 0) return res;
        res = strs[0];
        
        for(int i = 0; i < res.length(); i++){         
            for(int j = 1; j < strs.length; j++){
                if(i >= strs[j].length() || strs[j].charAt(i) != res.charAt(i)){
                    return res.substring(0, i);
                }
            }
        }
        
        return res;
    }

No comments:

Post a Comment