Соответствие строк первым n буквам двух строк

Поэтому для проблемы, с которой я сталкиваюсь, я хотел бы знать, как долго последовательность (начиная с индекса 0) двух строк "одинакова" - я думаю, было бы яснее просто привести пример;

  • Я хотел бы, чтобы метод возвращал 4, если две строки - "Йеллоустоун" и "Yelling" - это означает, что первые 4 символа двух строк совпадают ("Yell")

Есть ли более эффективный (по времени) способ сделать это, чем просто перебирать два слова? Могу я использовать какой-нибудь встроенный метод? (Для моей задачи я хочу избежать импорта любых пользовательских библиотек)

Источник

4 ответа

Решение

Я думаю, что самым быстрым подходом было бы использовать Binaray Search, который даст вам O(logn) сложность вместо O(n). Здесь n - длина наименьшей строки.

Подход прост в бинарном поиске. Ищите конец сходства для символа индекса в обеих строках. Например, если i - ваш индекс, тогда проверьте i+1 на наличие символа несходства, где символ в индексе i похож. И если дело обстоит именно так, верните i в качестве ответа. Или продолжайте искать в под-области.

редактировать

Добавление функции для лучшего понимания.

int lengthOfFirstSimilarCharacters(String str1, String str2) {
    int strlen1 = str1.length();
    int strlen2 = str2.length();
    if(strlen1 > strlen2){
        return lengthOfFirstSimilarCharacters(str2,str1);
    }
    int i = 0;
    int j = strlen1-1;
    while(i<=j){
        int mid = i + (j-i)/2;
        if(str1.charAt(mid) == str2.charAt(mid)) {
            if(mid+1<strlen1 && str1.charAt(mid+1) != str2.charAt(mid+1)){
                return mid+1;
            }
            i = mid+1;
        }else{
            j = mid-1;
        }
    }
    return i;
}
Источник

Вам не нужно перебирать оба текста. Переберите меньший и сравните символ с тем же индексом. сломаться, как и когда вы найдете несоответствие

String a ="Yellow";
String b= "Yelling";
String smaller = (a.length < b.length) ? a:b;
int ret =0;
for (index based on smaller ){
  compare character using charAt and if matching ret++, else break;
}
return ret;

// используем charAt вместе с equalsIgnoreCase, если хотим, чтобы он был без учета регистра. String.valueOf(a.charAt(индекс)). EqualsIgnoreCase(String.valueOf(b.charAt(индекс)))

Источник

Использование потоков

    String s1 = "Yellow";
    String s2 = "Yelling";
    int limit = (s1.length() > s2.length() ? s2.length() : s1.length()) - 1;
    int ret = IntStream.range(0, limit)
                .filter(i -> s1.charAt(i) != s2.charAt(i))
                .findFirst().orElse(-1);
    //-1 if the Strings are the same.
Источник

Исправление:

Ответ Сачина Чаухана действительно верен и лучше во время выполнения (т. Е. С помощью бинарного поиска для поиска первой разницы).

Я оставлю свой ответ, чтобы учесть более простое время программиста решения, для случаев, когда длина не имеет большого влияния (то есть относительно короткие строки), но простое решение было бы предпочтительным.

Вот оригинальный ответ:

Поскольку это простой цикл, я сомневаюсь, что любой встроенный метод будет в значительной степени улучшением во время "программирования" (и определенно не так уж много значительных улучшений во время выполнения).

Кстати, я не знаю такого Java-метода (возможно, какой-то внешней библиотеки, но вы заявили, что предпочли бы их избегать).

Код ссылки был бы чем-то вроде этого, я бы вообразил:

public int longestCommonPrefixLength(String s1, String s2) {

    if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) {
        return 0;
    }

    int commonPrefixLength = 0;

    for (int i = 0; i < Math.min(s1.length(), s2.length()); i++) {
        if (s1.charAt(i) == s2.charAt(i)) {
            commonPrefixLength++;
        } else {
            break;
        }
    }

    return commonPrefixLength;
}

Как видим, со всем многословием Java и моим стилем "ясности", это всего лишь 18 строк кода.:)

Отдохнув немного ясности, вы можете даже сократить for чтобы:

for (int i = 0; i < Math.min(s1.length(), s2.length()) && s1.charAt(i) == s2.charAt(i); i++, commonPrefixLength++);

на 6 строк меньше.

Чтобы довести это до (правильной) крайности:

public int longestCommonPrefixLength2(String s1, String s2) {
    if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0) return 0;
    int i = 0;
    for (; i < Math.min(s1.length(), s2.length()) && s1.charAt(i) == s2.charAt(i); i++);
    return i;
}

6 ЛОК:)

Кстати, что-нибудь любопытное

String класс имеет boolean regionMatches(int toffset, String other, int ooffset, int len) метод (который внутренне делает в значительной степени вышеупомянутое до заданного len) - вы также можете многократно увеличить len пока он больше не вернет истину, но это, конечно, не будет почти такой же эффективности.

Источник
Другие вопросы по тегам