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

Question

我知道 substring 是如何工作的，但我试图了解它在下面的代码中是如何工作的。目标是在字符串数组中找到最长的公共前缀。输入的字符串是 {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 到 length-1 将给出整个单词

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

public String substring(int beginIndex, int endIndex)
返回一个新字符串，它是该字符串的子字符串。
子字符串从指定的 beginIndex 开始并扩展到索引 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

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

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

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

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

您可以通过使用 来避免“创建对象”这一点strs[i].regionMatches(0, prefix, 0, someLength)，其中someLength是一个从 开始的 int prefix.length()，然后递减直到regionMatches返回 true。但这仍然是低效的，因为您一次递减它。

如果您以另一种方式进行操作会更容易：someLength从零开始，然后递增直到：

• 它等于 的长度prefix：someLength >= prefix.length()

• 它等于 的长度strs[i]：someLength >= strs[i].length()

• 该位置的相应字符不匹配：prefix.charAt(someLength) != strs[i].charAt(someLength)

这基本上就是startsWith这样做的，但是通过“你自己”做，你会发现字符串不同的位置。

然后，用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);

}