我想了解子串调用在这段代码中是如何工作的？

Question

我知道子字符串是如何工作的，但我试图在下面的代码中了解它是如何工作的。目标是在字符串数组中找到最长的公共前缀。输入的字符串是 {flower, flow, fleece}。看起来 substring 每次都只是取花的整个词，当它不为 0 时，因为 0 到 length-1 将给出整个词。

 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;
}

输出为fl。我只是想了解原因。

Answer 1

0 to length-1 is going to give the entire word

不，它 returns 除了最后一个字符之外的单词。
来自：https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#substring(int,%20int)

public String substring(int beginIndex, int endIndex)
Returns a new string that is a substring of this string.
The substring begins at the specified beginIndex and extends to the character at index endIndex - 1.

所以代码所做的是在每次迭代时使用以下行修剪最后一个字符：

prefix = prefix.substring(0, prefix.length() - 1);

直到它找到一个共同的前缀。

Answer 2

substring()中的endIndex是独占的。因此，代码所做的是从前缀变量中删除最后一个字符。

String hello = "hello";
System.out.println(hello.substring(0,hello.length));
// hello
System.out.println(hello.substring(0,hello.length - 1));
// hell

Answer 3

虽然这不是您要问的直接问题，但值得一提的是，使用 indexOf 和 substring 并不是解决此问题的好方法。

strs[i].indexOf(prefix) != 0 是检查字符串是否以某物开头的低效方法。这是因为如果它发现字符串不是以 prefix 开头，它会继续在其他位置搜索匹配项 - 如果它出现在那里并不重要。

更有效的检查是 !strs[i].startsWith(prefix)：一旦发现字符串不以前缀开头，它就会停止。

然后，使用substring从字符串末尾切掉一个字符也是低效的：每次切掉一个字符，都会创建一个新字符串，然后您再次检查；但是在找到匹配的前缀之前，您可能必须砍掉很多个单独的字符。

您可以通过使用 strs[i].regionMatches(0, prefix, 0, someLength) 来避免其中的 "creating objects" 位，其中 someLength 是一个从 prefix.length() 开始的整数，并且您递减直到 regionMatches returns 是的。但这仍然是低效的，因为你一次递减一个。

如果换一种方式会更容易：从 someLength 零开始，然后递增直到：

等于prefix的长度：someLength >= prefix.length()
等于strs[i]的长度：someLength >= strs[i].length()
该位置对应的字符不匹配：prefix.charAt(someLength) != strs[i].charAt(someLength)

这基本上就是 startsWith 所做的，但是通过这样做 "yourself"，您可以找出字符串不同的位置。

然后，用prefix = prefix.substring(0, someLength);一口气砍掉。或者根本不砍它：你可以简单地存储公共前缀的长度，并在最后做一次子字符串。

代码看起来像这样：

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    int prefixLength = strs[0].length();
    for (int i = 1; i < strs.length; i++) {
        int s = 0;
        while (s < prefixLength
            && s < strs[i].length()
            && strs[0].charAt(s) == strs[i].charAt(s)) {
          ++s;
        }
        prefixLength = s;
    }
    return strs[0].substring(0, prefixLength);
}

我想了解子串调用在这段代码中是如何工作的？

I'm trying to understand how substring call is working in this code?

java

substring

indexof