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

Question

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

• Я хотел бы способ вернуть 4, если две строки «Йеллоустоун» и «Вопли» - значение, первые 4 символа матча две строки («Yell»)

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

Answer 1

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

Этот подход прост в двоичном поиске. Ищите конец подобия для символа индекса в обеих строках. Например, если i является вашим индексом, тогда проверьте i + 1 для символа сходства, где символ в индексе 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; 
} 

Answer 2

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

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; 

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

Answer 3

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

Ответ на Sachin Чаухана действительно правильно и лучше (т. е. используя двоичный поиск для поиска первой разницы).

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

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

Как это простой цикл, я сомневаюсь, что любой встроенный метод будет много «программиста» -time улучшения (и, безусловно, не так много времени выполнения повышения ценности для говоря).

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

Reference код будет что-то вдоль этих линий, я бы себе:

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 LOC :)

Что любопытно, кстати:

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

Answer 4

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

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.