java - ` (strs[i].indexOf(prefix) != 0) ` 在查找 LongestCommonPrefix

Question

我看了LongestCommonPrefix这样的解决方案

Longest Common Prefix - LeetCode

 public String longestCommonPrefix(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) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}

对于while (strs[i].indexOf(prefix) != 0)，如果prefix不为空，表达式会一直返回True；

如何得出 prefix = prefix.substring(0, prefix.length() - 1); 的结论，我假设了 while (strs[i].indexOf(prefix) ! = 0) 什么也没做。

Answer 1

这个算法的思路是:

1. 首先假设第一个单词是prefix，然后我们将检查prefix 是否是所有其他单词的前缀。

2. 如果 strs[i].indexOf(prefix) != 0 表示它不是以 prefix 开头。所以我们应该减少一点前缀(删除最后一个字符)，即:prefix = prefix.substring(0, prefix.length() - 1);

3. 我们不断地这样做，利用所有检查过的词，或者前缀有被剪切成''(这就是它被称为水平扫描的原因)

希望对您有所帮助，如果您还有其他问题，请发表评论。 :)