[LeetCode]--14. Longest Common Prefix

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

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

提交通过之后这个又可以看别人写的优秀程序。

Approach #1 (Horizontal scanning)

public String longestCommonPrefix(String[] strs) { if (strs.length == 0) return ""; String prefix = strs[0]; for (int i = 1; i < strs.length; i++) while (strs[i].indexOf(prefix) != 0) { prefix = prefix.substring(0, prefix.length() - 1); if (prefix.isEmpty()) return ""; } return prefix; }

这段代码我是打断点跟着才看懂的，每次indexOf的返回值是0，也就是说包含这个子串才跳出，不然一个字符一个字符的减。直到找到为止。这里介绍一下indexOf的用法。

indexOf()定义和用法 indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置。indexOf()的用法：返回字符中indexof（string）中字串string在父串中首次出现的位置，从0开始！没有返回-1；方便判断和截取字符串！ 语法 stringObject.indexOf(searchvalue,fromindex) 参数 描述

searchvalue 必需。规定需检索的字符串值。

fromindex 可选的整数参数。规定在字符串中开始检索的位置。它的合法取值是 0到 - 1。如省略该参数，则将从字符串的首字符开始检索。

说明 该方法将从头到尾地检索字符串 stringObject，看它是否含有子串 searchvalue。开始检索的位置在字符串的 fromindex 处或字符串的开头（没有指定 fromindex 时）。如果找到一个 searchvalue，则返回 searchvalue 的第一次出现的位置。stringObject 中的字符位置是从 0 开始的。 提示和注释 注释：indexOf() 方法对大小写敏感！ 注释：如果要检索的字符串值没有出现，则该方法返回 -1。 实例 在本例中，我们将在 “Hello world!” 字符串内进行不同的检索：

var str="Hello world!"; document.write(str.indexOf("Hello") + " "); document.write(str.indexOf("World") + " "); document.write(str.indexOf("world"));

以上代码的输出： 0 -1 6

Approach #2 (Vertical scanning)

public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) 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 (i == strs[j].length() || strs[j].charAt(i) != c) return strs[0].substring(0, i); } } return strs[0]; }

Approach #3 (Divide and conquer)

public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return ""; return longestCommonPrefix(strs, 0 , strs.length - 1); } private String longestCommonPrefix(String[] strs, int l, int r) { if (l == r) { return strs[l]; } else { int mid = (l + r)/2; String lcpLeft = longestCommonPrefix(strs, l , mid); String lcpRight = longestCommonPrefix(strs, mid + 1,r); return commonPrefix(lcpLeft, lcpRight); } } String commonPrefix(String left,String right) { int min = Math.min(left.length(), right.length()); for (int i = 0; i < min; i++) { if ( left.charAt(i) != right.charAt(i) ) return left.substring(0, i); } return left.substring(0, min); }

Approach #4 (Binary search)

public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return ""; int minLen = Integer.MAX_VALUE; for (String str : strs) minLen = Math.min(minLen, str.length()); int low = 1; int high = minLen; while (low <= high) { int middle = (low + high) / 2; if (isCommonPrefix(strs, middle)) low = middle + 1; else high = middle - 1; } return strs[0].substring(0, (low + high) / 2); } private boolean isCommonPrefix(String[] strs, int len){ String str1 = strs[0].substring(0,len); for (int i = 1; i < strs.length; i++) if (!strs[i].startsWith(str1)) return false; return true; }

Further Thoughts / Follow up

public String longestCommonPrefix(String q, String[] strs) { if (strs == null || strs.length == 0) return ""; if (strs.length == 1) return strs[0]; Trie trie = new Trie(); for (int i = 1; i < strs.length ; i++) { trie.insert(strs[i]); } return trie.searchLongestPrefix(q); } class TrieNode { // R links to node children private TrieNode[] links; private final int R = 26; private boolean isEnd; // number of children non null links private int size; public void put(char ch, TrieNode node) { links[ch -'a'] = node; size++; } public int getLinks() { return size; } //assume methods containsKey, isEnd, get, put are implemented as it is described //in https://leetcode.com/articles/implement-trie-prefix-tree/) } public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } //assume methods insert, search, searchPrefix are implemented as it is described //in https://leetcode.com/articles/implement-trie-prefix-tree/) private String searchLongestPrefix(String word) { TrieNode node = root; StringBuilder prefix = new StringBuilder(); for (int i = 0; i < word.length(); i++) { char curLetter = word.charAt(i); if (node.containsKey(curLetter) && (node.getLinks() == 1) && (!node.isEnd())) { prefix.append(curLetter); node = node.get(curLetter); } else return prefix.toString(); } return prefix.toString(); } }

LeetCode官方参考链接