leetcode14最長公共字首多解法

題目連結

解法一：按列比較，選第一個字元為比較對象，若長度達到所有字元串中最短的字元長度，或者有不符合的出現，傳回結果。時間擊敗了7.28%的人。

class Solution {
        public String longestCommonPrefix(String[] strs) {
            String s = "";
            if (strs.length < 1)
                return "";
            for (int i = 0; i < strs[0].length(); i++) {
                char c = strs[0].charAt(i);
                for (int j = 1; j < strs.length; j++) {
                    if (strs[j].length() <= i || strs[j].charAt(i) != c)
                        return s;
                }
                s += c;
            }
            return s;
        }
    }
           

解法二：分治算法，将字元串數組分兩半來算，然後再比較兩個兩半得到的結果,擊敗了99%。

class Solution {
        public String longestCommonPrefix(String[] strs) {
            int len = strs.length;
            if (len < 1)
                return "";
            return dfs(strs, 0, len - 1);
        }

        private String dfs(String[] strs, int begin, int end) {
            if (end <= begin) {
                return strs[begin];
            }
            int mid = (begin + end) >> 1;
            String a = dfs(strs, begin, mid);
            String b = dfs(strs, mid + 1, end);

            int length = Math.min(a.length(), b.length());
            int index = 0;
            while (index < length && a.charAt(index) == b.charAt(index)) {
                index++;
            }
            return a.substring(0, index);
        }
    }
           

解法三：在評論區找到的一個巧妙解法，排序字元串數組，再比較第一個和最後一個即可,擊敗87%。

class Solution {
        public String longestCommonPrefix(String[] strs) {
            if (strs.length < 1)
                return "";
            Arrays.sort(strs);
            int index = 0;
            int min = Math.min(strs[0].length(), strs[strs.length - 1].length());
            for (int i = 0; i < min; i++) {
                if (strs[0].charAt(i) != strs[strs.length - 1].charAt(i))
                    break;
                index++;
            }
            return strs[0].substring(0, index);
        }
    }
           

解法四：使用字典樹（trim）算法，這個模闆還是很有用的，需要根據題目需求在最基礎的模闆做一些修改，在細節處debug找了很久，最後擊敗了85%。

class Solution {
        trie root;

        class trie {
            int flag;
            trie[] cnt;

            public trie() {
                this.flag = 0;
                cnt = new trie[26];
                for (int i = 0; i < 26; i++)
                    cnt[i] = null;
            }

            public void insert(String s) {
                trie tmp = root;
                for (int i = 0; i < s.length(); i++) {
                    int num = s.charAt(i) - 'a';
                    if (tmp.cnt[num] == null) {
                        tmp.cnt[num] = new trie();
                    }
                    tmp = tmp.cnt[num];
                    tmp.flag++;
                }
            }

            public int find(String s, int n) {
                trie tmp = root;
                for (int i = 0; i < s.length(); i++) {
                    int num = s.charAt(i) - 'a';
                    if (tmp.cnt[num].flag < n || tmp.cnt[num] == null)
                        return i;
                    tmp = tmp.cnt[num];
                }
                return s.length();
            }
        }

        public String longestCommonPrefix(String[] strs) {
            //trie樹
            if (strs.length < 1 || strs == null)
                return "";
            root = new trie();
            for (int i = 0; i < strs.length; i++) {
                root.insert(strs[i]);
            }
            root.flag = strs.length;
            int len = root.find(strs[0], strs.length);
            return strs[0].substring(0, len);
        }
    }
           

雖然是一道簡單題目，前面兩種算法很快就想出了，但是後面複習了分治算法和字典樹算法，其中分治很快自己寫出來了，字典樹是忘記了又去看了一遍自己寫的，一下午就過了，還算有點收獲。