Блог

Я пытаюсь определить, редактировалась ли строка только один раз. Когда я ввожу следующие строки (см. Код ниже), вывод неверен. Программа должна напечатать, что строка была отредактирована только один раз, и это не то, что я вижу на своем экране. Кто-нибудь может мне помочь?

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

Ваша проблема здесь в том, что вы проходите только по длине одной строки, в то время как вы должны проходить через 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/

Я предполагаю, что вы хотите проверить ровно одну правку, отклонив строки, содержащие ноль или более.

Учитывая две строки ( s1, s2 ), длина которых s1 больше или равна s2 (измените параметры, если это не так), мы можем проверить наличие одного изменения, используя следующее:

1. Отфильтруйте случаи, когда разница в длине превышает 1.
2. Используйте первую последовательность одинаковых символов.
3. Если вы дошли до конца s2 , то проверьте, что s1 это дольше. Если это не так, то s1 == s2 и условие не выполнено.
4. Используйте вторую последовательность одинаковых символов. Если s1 он длиннее (на единицу), то нам нужно использовать смещение 1 при доступе к символам s2 .
5. Если вы достигли конца 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