LeetCode之 14. Longest Common Prefix

题意：

给一个字符串数组，求字符串中最大的前缀

思路：

map<String,Integer>逐步保存前缀，意思是，对第i个字符串，当前的前缀从map中取出来的val == i， 那么这个前缀是合法的， 如果val!=i ，即不合法，那么退出这个字符串。最后去map中取出最长的且val合法的即可

map的遍历方式：

1、迭代器迭代keySet（），效率低

Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
for (Integer key : map.keySet()) { Integer value = map.get(key); System.out.println("Key = " + key + ", Value = " + value);

2、for each遍历map的key或val

for (Integer key : map.keySet()) { System.out.println("Key = " + key); 
} 
//遍历map中的值 
for (Integer value : map.values()) { System.out.println("Value = " + value); 

代码：(19ms)

 public String longestCommonPrefix(String[] strs) {if(strs.length == 1)return strs[0];Map<String, Integer> map = new HashMap<>();for(int i=0;i<strs.length;i++){StringBuilder sb = new StringBuilder();for(int j=0;j<strs[i].length();j++){sb.append(strs[i].charAt(j));if(i == 0){map.put(sb.toString(),1);}else {Integer val = map.get(sb.toString());if (val == null || val != i )break;map.put(sb.toString(), val + 1);
//                    System.out.println(sb + "   " + val);}}}Iterator<String> it = map.keySet().iterator();Integer cnt = 0;String ansSb = "";while (it.hasNext()){String key = it.next();Integer val = map.get(key);if(val == strs.length && key.length() > ansSb.length()) {cnt = val;ansSb = key;
//                System.out.println(ansSb + "   " + cnt);}}return ansSb;}

别人博客中更快的方法(8ms),收获最大的是源码的学习能力

https://blog.csdn.net/u014629433/article/details/51680523
另外 博主还根据indexOf底层源码进行优化，很值得学习

用strs[0]作为模板prefix , 当prefix不等于strs[i]的前缀时，prefix尾巴减一，最后保留下来的一定是我们要的答案

 private   String method(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){
//                System.out.println(prefix + "   " + strs[i].indexOf(prefix));prefix = prefix.substring(0,prefix.length()-1);}}return prefix;}