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

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&nbsp;=&nbsp;prefix.substring(0,&nbsp;prefix.length()&nbsp;-&nbsp;1);直到找到一个共同的前缀。

Answer 2

substring() 中的 endIndex 是唯一的。因此，代码所做的是从前缀变量中删除最后一个字符。String hello = "hello";System.out.println(hello.substring(0,hello.length));// helloSystem.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&nbsp;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) {&nbsp; &nbsp; if (strs.length == 0) return "";&nbsp; &nbsp; int prefixLength = strs[0].length();&nbsp; &nbsp; for (int i = 1; i < strs.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; int s = 0;&nbsp; &nbsp; &nbsp; &nbsp; while (s < prefixLength&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; && s < strs[i].length()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; && strs[0].charAt(s) == strs[i].charAt(s)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++s;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; prefixLength = s;&nbsp; &nbsp; }&nbsp; &nbsp; return strs[0].substring(0, prefixLength);}