题目

14. 最长公共前缀

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

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

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

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

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

题解

代码

import java.util.*;

public class code14 {
    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String ans = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j;
            for (j = 0; j < strs[i].length() && j < ans.length(); j++) {
                if (strs[i].charAt(j) != ans.charAt(j)) {
                    break;
                }
            }
            ans = ans.substring(0, j);
            // 只要任意两个字符串没有公共前缀，则该字符串数组就不可能再有公共前缀了。
            if (ans.equals("")) {
                return ans;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        String s1[] = { "flower", "flow", "flight" };
        String str1 = longestCommonPrefix(s1);
        System.out.println(str1);

        String s2[] = { "dog", "racecar", "car" };
        String str2 = longestCommonPrefix(s2);
        System.out.println(str2);
    }
}

参考

  1. 画解算法：14. 最长公共前缀
  2. Leetcode 14. 最长公共前缀
  3. 14. 最长公共前缀——题解一