14. 最长公共前缀

顺序比较字符串

14. 题目链接-来源：力扣（LeetCode）（简单）

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”

思路：

这题的解法形象地理解就是给你并排放几根烤串，你拿一根签子垂直这些烤串，一排排把东西划下来。第一排全是豆腐，第二排全是鸡柳，第三排全是板筋，第四排，出现不一样的了有骨肉相连、有蚕蛹，那么前三排一样的部分『豆腐』、『鸡柳』、『板筋』就是所求的公共前缀。这种解法可以称之为『垂直遍历』或者『横向遍历』或者随便什么名字。
与之相对应的就是『平行遍历』，先遍历记录第一串，再遍历对比第二串，发现到不同之处就截停，丢弃余下部分，只保留相同部分，继续比对。
时间复杂度：O(nm) n是字符串个数，m是公共前缀长度。但实际上如果第一串字符串是最长的，第二种方法仍然会把它遍历完，但是多出来的部分不影响mn的数量级就是了。
空间复杂度:O(m+n)（垂直遍历） O(m)（平行遍历）

实现：

class Solution {
    class ListNode {
        char key;
        ListNode next;
        ListNode(char c) {
            key = c;
            next = null;
        }
    }
    
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        ListNode trie = new ListNode(' ');
        
        String s = strs[0];
        int len = s.length();
        ListNode cur = trie;
        for (int i = 0; i < len; i++) {
            cur.next = new ListNode(s.charAt(i));
            cur = cur.next;
        }
        
        for (int i = 1; i < n; i++) {
            cur = trie;
            s = strs[i];
            len = s.length();
            if (len == 0) {
                trie.next = null;
            }
            for (int j = 0; j < len; j++) {
                if (cur.next != null && cur.next.key == s.charAt(j)) {
                    cur = cur.next;
                    if (j >= len - 1) {
                        cur.next = null;
                    }
                } else {
                    cur.next = null;
                    break;
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (cur = trie.next; cur != null; cur = cur.next) {
            sb.append(cur.key);
        }
        
        return sb.toString();
    }
}