Я пытаюсь понять, как работает вызов подстроки в этом коде?

Question

Я знаю, как работает подстрока, но я пытался понять, как она работает, в приведенном ниже коде. Цель состояла в том, чтобы найти самый длинный общий префикс в массиве строк. Ввод строки был {цветок, поток, руно}. Похоже, что подстрока просто берет все слово цветка, когда это не 0, каждый раз, так как от 0 до длины-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

endIndex в substring () является эксклюзивным.Итак, код выполняет удаление последнего символа из префиксной переменной.

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

Answer 2

0 в длину-1 собирается дать все слово

Нет, он возвращает слово, кроме последнего символа.
От: https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#substring(int,%20int)

public String substring (int beginIndex, int endIndex)
Возвращает a новая строка, которая является подстрокой этой строки.
Подстрока начинается с указанного beginIndex и распространяется на символ в индекс endIndex - 1.

Итак, код выполняет обрезку последнего символа на каждой итерации с помощью этой строки:

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

пока не найдет общий префикс.

Answer 3

Хотя это не совсем то, о чем вы спрашиваете, стоит отметить, что использование indexOf и substring не является хорошим способом приблизиться к этому.

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