最长公共前缀

题目

思路

• 思路一：前缀树构建公共前缀
• 思路二：横向扫描：前两个字符串找公共子串，将其结果和第三个字符串找公共子串……直到最后一个串。时间性能为O(n*m)。

  代码

  ```java //前缀树 Map map = new HashMap<>(); public String longestCommonPrefix(String[] strs) {

    for (String s : strs) {
        if (s.length() == 0) return "";
        Map<Character, Solution> p = map;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            p.putIfAbsent(ch, new Solution());
            p = p.get(ch).map;
            if (i == s.length() - 1) p.put('#', new Solution());
        }
    }
    StringBuilder res = new StringBuilder("");
    while (map != null && map.size() == 1) {
        char key = ' ';
        for (char ch : map.keySet()) {
            key = ch;
        }
        if (key == '#') break;
        res.append(key);
        map = map.get(key).map;
    }
    return res.toString();

  } //横向扫描 public String longestCommonPrefix(String[] strs) {

    if (strs.length == 0) return "";
    String ans = strs[0];
    for(int i =1;i<strs.length;i++) {
        int j=0;
        for(;j<ans.length() && j < strs[i].length();j++) {
            if(ans.charAt(j) != strs[i].charAt(j))
                break;
        }
        ans = ans.substring(0, j);
        if(ans.equals(""))
            return ans;
    }
    return ans;
  

  }

``` 最长公共前缀