1. 先把每个字符串分解成一个前缀列表; 比如 abbadf, 可以分解得到 a, ab, abb, abba, ... abbadf;
2. 得到的所有的前缀列表拉平连在一起,组成一个新的列表,然后排序;
3. 然后计算每一个前缀出现的次数;
4. 然后从长到短找出现次数为n的前缀,就可以答案;
假设字符最长为m,那么可以分解出m - 1个前缀码,所以得到的前缀码列表长为 n * m; 排序(n * m) log(n * m); 计数 n * m. 应该比直接计算要快一些。
//求最长的公共前缀。 char *xtqz(char **arr,unsigned int length) { unsigned int i=0;//指示应该匹配第i个字符串 unsigned int j=0;// 指示应该匹配第j个字符 char tmp1; //第一个字符串的第j个字符 char *result=NULL;//返回的结果 也就是公共前缀 unsigned int length2=strlen(arr[0]);//控制匹配字符的次数 for(;j<length2;j++) { tmp1=*(arr[0]+j);//得到第一个字符的第j个字符,用来跟后面的字符串的第j个字符匹配 for(i=1;i<length;i++) { if(j>=strlen(arr[i]))//也许第一个字符串长度不是最短的,如果有比它更短的就应该退出匹配 break; if(*(arr[i]+j)!=tmp1) //如果当前字符串的第j字符与第一个字符串的第j个字符不匹配就退出 break; } if(i!=length)//这就是匹配失败后的情况 break; } if(j>0) { result=(char *)malloc(sizeof(j+1)); //匹配第j个失败,所以就分配j+1个内存 strncpy(result,arr[0],j);//复制第一个字符串的前j个到结果并把末尾价格\0 result[j]='\0'; } return result; } int main() { char *arr[] = {"abcdef","abcdea","abccdde","abcbadf"}; printf("%s",xtqz(arr,4)); return 0; }
就一个一个来,跑一遍就完了,这玩意还有什么鬼神莫测的办法不成?
前提:取最长公共前缀
零:循环求最短单词
一:假设最短单词为最长前缀
二:循环所有单词匹配前缀
三:如果有不匹配的,最短单词末尾去一个字母,继续第二步
四:当循环完毕,最短单词剩下的就是公共前缀了。
trie树解法:
/** * 使用trie树 */ private static class Trie{ private Node root; private int max = 0; private int stringLength = 0; private String strings = ""; private class Node { int count; Node[] next; public Node() { this.count = 0; next = new Node[57]; } } public void put(String string) { root = put(root, string); } private Node put(Node node, String chars) { if (node == null) node = new Node(); Node p = node; this.stringLength += 1; for (int i = 0; i < chars.length(); i++) { int id = chars.charAt(i) - 'A'; // System.out.println("id: " + id + " char: " + chars.charAt(i)); if (p.next[id] == null) { p.next[id] = new Node(); } p.next[id].count += 1; p = p.next[id]; } return node; } public String getMax() { getMax(root); return this.strings; } private void getMax(Node node) { Node p = node; for (int i = 0; i < 57; i++) { if (p.next[i] != null && p.next[i].count == stringLength) { char c = (char) (i + 'A'); strings += c; getMax(p.next[i]); break; } } } } /** * @param strs: A list of strings * @return: The longest common prefix */ public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) { return ""; } Trie t = new Trie(); for (String s : strs) { t.put(s); } return t.getMax(); }
/** * 另一种解法,两个两个的比 * @param strs * @return */ public String longestCommonPrefix2(String[] strs) { if (strs == null || strs.length == 0) { return ""; } if (strs.length == 1) { return strs[0]; } String ret = minCommonPrexString(strs[0], strs[1]); for (int i = 2; i < strs.length; i++) { ret = minCommonPrexString(strs[i], ret); } return ret; } /** * 得到两个字符串最长的公共前缀长度 * @param str1 * @param str2 * @return */ private String minCommonPrexString(String str1, String str2) { if (str1 == null || str2 == null || str1 == "" || str2 == "") { return ""; } int len1 = str1.length(); int len2 = str2.length(); int min = Math.min(len1, len2); int ret = 0; for (int i = 0; i < min; i++) { if (str1.charAt(i) != str2.charAt(i)) { return str1.substring(0, ret); } ret += 1; } return str1.substring(0, ret); }
1. 先把每个字符串分解成一个前缀列表; 比如 abbadf, 可以分解得到 a, ab, abb, abba, ... abbadf;
2. 得到的所有的前缀列表拉平连在一起,组成一个新的列表,然后排序;
3. 然后计算每一个前缀出现的次数;
4. 然后从长到短找出现次数为n的前缀,就可以答案;
假设字符最长为m,那么可以分解出m - 1个前缀码,所以得到的前缀码列表长为 n * m; 排序(n * m) log(n * m); 计数 n * m. 应该比直接计算要快一些。
引用来自“BlueWoods”的评论
1. 先把每个字符串分解成一个前缀列表; 比如 abbadf, 可以分解得到 a, ab, abb, abba, ... abbadf;
2. 得到的所有的前缀列表拉平连在一起,组成一个新的列表,然后排序;
3. 然后计算每一个前缀出现的次数;
4. 然后从长到短找出现次数为n的前缀,就可以答案;
假设字符最长为m,那么可以分解出m - 1个前缀码,所以得到的前缀码列表长为 n * m; 排序(n * m) log(n * m); 计数 n * m. 应该比直接计算要快一些。
就一个一个来,跑一遍就完了,这玩意还有什么鬼神莫测的办法不成?
前提:取最长公共前缀
零:循环求最短单词
一:假设最短单词为最长前缀
二:循环所有单词匹配前缀
三:如果有不匹配的,最短单词末尾去一个字母,继续第二步
四:当循环完毕,最短单词剩下的就是公共前缀了。
trie树解法: