#java #arrays #string #edit
Вопрос:
Я пытаюсь определить, редактировалась ли строка только один раз. Когда я ввожу следующие строки (см. Код ниже), вывод неверен. Программа должна напечатать, что строка была отредактирована только один раз, и это не то, что я вижу на своем экране. Кто-нибудь может мне помочь?
public static void main(String[] args) {
String str1 = "cat";
String str2 = "ca";
char[] arr1 = str1.toCharArray();
char[] arr2 = str2.toCharArray();
int n = str1.length();
int m = str2.length();
if (stringWasEdited(str1, str2, arr1, arr2, m, n)) {
System.out.print("The string was edited only once.");
} else {
System.out.print("The string was not edited or was edited more than once.");
}
}
private static boolean stringWasEdited(String str1, String str2, char[] arr1, char[] arr2, int m, int n) {
int count = 0;
if (Math.abs(m - n) > 1) {
return false;
}
for (int i = 0; i < m; i ) {
if (arr1[i] != arr2[i]) {
count ;
}
if (m > n || n > m) {
count ;
}
}
if (count > 1 || count == 0) {
return false;
}
return true;
}
}
Комментарии:
1. проверьте это geeksforgeeks.org/…
2. Для более общих задач посмотрите на расстояние Левенштейна
Ответ №1:
Ваша проблема здесь в том, что вы проходите только по длине одной строки, в то время как вы должны проходить через i < m amp;amp; i:
static boolean isEditDistanceOne(String s1,
String s2)
{
// Find lengths of given strings
int m = s1.length(), n = s2.length();
// If difference between lengths is
// more than 1, then strings can't
// be at one distance
if (Math.abs(m - n) > 1)
return false;
int count = 0; // Count of edits
int i = 0, j = 0;
while (i < m amp;amp; j < n)
{
// If current characters don't match
if (s1.charAt(i) != s2.charAt(j))
{
if (count == 1)
return false;
// If length of one string is
// more, then only possible edit
// is to remove a character
if (m > n)
i ;
else if (m< n)
j ;
else // Iflengths of both strings
// is same
{
i ;
j ;
}
// Increment count of edits
count ;
}
else // If current characters match
{
i ;
j ;
}
}
// If last character is extra
// in any string
if (i < m || j < n)
count ;
return count == 1;
}
Ссылка для справки: https://www.geeksforgeeks.org/check-if-two-given-strings-are-at-edit-distance-one/
Ответ №2:
Я предполагаю, что вы хотите проверить ровно одну правку, отклонив строки, содержащие ноль или более.
Учитывая две строки ( s1, s2
), длина которых s1
больше или равна s2
(измените параметры, если это не так), мы можем проверить наличие одного изменения, используя следующее:
- Отфильтруйте случаи, когда разница в длине превышает 1.
- Используйте первую последовательность одинаковых символов.
- Если вы дошли до конца
s2
, то проверьте, чтоs1
это дольше. Если это не так, тоs1 == s2
и условие не выполнено. - Используйте вторую последовательность одинаковых символов. Если
s1
он длиннее (на единицу), то нам нужно использовать смещение 1 при доступе к символамs2
. - Если вы достигли конца
s1
, то условие выполнено.
Вышесказанное переведено на Java (Ideon):
static boolean hasOneEdit(String s1, String s2)
{
// ensure s1 is longer than or equal to s2
if(s1.length() < s2.length()) return hasOneEdit(s2, s1);
// difference in length cannot be more than one
if(s1.length() - s2.length() > 1) return false;
int pos = 0;
// consume 1st sequence of equal characters
for(; pos < s2.length() amp;amp; s1.charAt(pos) == s2.charAt(pos); pos );
// if we reached the end of s2, s1 has to be longer (by 1)
if(pos == s2.length()) return pos < s1.length();
// offset into s2 depends on whether strings are equal in length
int off = s1.length() - s2.length();
// consume 2nd sequence of equal characters
for(pos = 1; pos < s1.length() amp;amp; s1.charAt(pos) == s2.charAt(pos-off); pos );
// did we reach the end of s1?
return pos == s1.length();
}
И небольшая программа тестирования:
public static void main(String[] args)
{
String s1 = "dirigible";
for(int i=0; i<s1.length(); i )
{
String s2 = s1.substring(0, i) s1.substring(i 1);
test(s1, s2, true);
for(int j=0; j<s2.length(); j )
{
String s3 = s2.substring(0, j) "x" s2.substring(j 1);
test(s1, s3, false);
}
}
for(int i=0; i<s1.length(); i )
{
String s2 = s1.substring(0, i) "x" s1.substring(i 1);
test(s1, s2, true);
for(int j=0; j<s2.length(); j )
{
String s3 = s2.substring(0, j) s2.substring(j 1);
test(s1, s3, j == i);
}
}
}
static void test(String s1, String s2, boolean check)
{
boolean result = hasOneEdit(s1, s2);
System.out.println((result == check ? "PASS" : "FAIL") ": " s1 " " s2 " = " check);
}
Выход:
PASS: dirigible irigible = true
PASS: dirigible xrigible = false
PASS: dirigible ixigible = false
PASS: dirigible irxgible = false
PASS: dirigible irixible = false
<Truncated>
PASS: dirigible dirgiblx = false
PASS: dirigible diriiblx = false
PASS: dirigible dirigblx = false
PASS: dirigible dirigilx = false
PASS: dirigible dirigibx = false
PASS: dirigible dirigibl = true