最长公共前缀

QUESTION:

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

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

示例 1:

输入: [“flower”,”flow”,”flight”] 输出: “fl” 示例 2:

输入: [“dog”,”racecar”,”car”] 输出: “” 解释: 输入不存在公共前缀。 说明:

所有输入只包含小写字母 a-z 。

EXPLANATION:

思路:既然是求公共的前缀,那么就可以一个字符一个字符的比对。第一个和第二得到公共的,再和第三个比对。
1.将第一个字符串作为公共前缀
2.与第二个字符串进行比对,得到公共的部分
3.不断循环到最后

SOLUTION:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0) return "";
        Queue<Character> queue = new ArrayDeque<>();
        for(char c:strs[0].toCharArray()) queue.add(c);
        for(int i = 1;i<strs.length;i++){
            Queue<Character> tmp = new ArrayDeque<>();
            for(char c:strs[i].toCharArray()){
                if(!queue.isEmpty()){
                    Character poll = queue.poll();
                    if(poll==c) tmp.add(poll);
                    else break;
                }
            }
            queue = tmp;
            if(queue.isEmpty()) return "";
        }
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) sb.append(queue.poll());
        return sb.toString();
    }
}