leetcode [#14]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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

---

解决方案

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        int N = strs.length;
        if(N == 0) return "";
        if(N == 1) return strs[0];
        StringBuilder builder = new StringBuilder();
        for(int i = 0; i < N - 1; i++){
            int len1 = strs[i].length();
            int len2 = strs[i+1].length();
            int commonLen = Math.min(len1,len2);
            StringBuilder temp = new StringBuilder();
            for(int m = 0; m < commonLen; m++){
                if(strs[i].charAt(m) == strs[i+1].charAt(m)){
                    temp.append(strs[i].charAt(m));
                } else {
                    break;
                }
            }
            int tempLen = temp.length();
            int builderLen = builder.length();

            if(i == 0){
                builder = temp;
            } else {
                if(tempLen < builderLen){
                    builder = builder.delete(tempLen, builderLen);
                }
            }
        }
        return  builder.toString();
    }
}

---

注意事项

1. 依次比较数组中每两个元素的最长前缀。第一个和第二个元素的最长前缀默认保存入builder，从第二个和第三个元素的比较结果开始，如果最长前缀比builder长，则不做操作，因为更长的部分无法作为之前其他元素的前缀，对整体结果没有意义；如果最长前缀比builder短，则要将builder的长度缩短相应的位数，因为之前的最长前缀不能作为当前元素的前缀。