Помогите с равенством строк в Java - PullRequest
Новая
       6

Помогите с равенством строк в Java

1 голос
/ 07 июня 2010

Следующая функция принимает 2 строки, 2-я (не 1-я), возможно, содержащая * (звездочки). * является заменой строки (пустой, 1 символ или более), она может появиться (только в s2) один раз, дважды, больше или не отображаться вообще, она не может быть смежной с другой * (ab**c), проверять это не нужно. 

public static boolean samePattern(String s1, String s2)

Возвращает true, если строки имеют одинаковый шаблон. Он должен быть рекурсивным, не использовать циклы, статические или глобальные переменные. Также запрещено использовать метод equals в классе String. Можно использовать локальные переменные и перегрузку метода. Можно использовать только эти методы: charAt(i), substring(i), substring(i, j), length().

Примеры: 

1: TheExamIsEasy; 2: "The*xamIs*y" ---> true
1: TheExamIsEasy; 2: "Th*mIsEasy*" ---> true
1: TheExamIsEasy; 2: "*" ---> true
1: TheExamIsEasy; 2: "TheExamIsEasy" ---> true
1: TheExamIsEasy; 2: "The*IsHard" ---> FALSE

Я застрял в этом вопросе на много часов! Мне нужно решение на Java, пожалуйста, помогите мне.

Ответы [ 2 ]

5 голосов
/ 07 июня 2010

Похоже, вы может хотите регулярные выражения .

Шаблон регулярного выражения .+ эквивалентен вашему *.

Но тогда у вас будут две проблемы.

2 голосов
/ 07 июня 2010

Ниже приведено рекурсивное решение вашей проблемы в Java без цикла: 

static boolean samePattern(String s1, String s2) {
    return
        s2.isEmpty() ?
            s1.isEmpty()
            :
        s2.charAt(0) == '*' ?
            samePattern(s1, s2.substring(1))
            || (!s1.isEmpty() && samePattern(s1.substring(1), s2))
            :
        !s1.isEmpty() && s2.charAt(0) == s1.charAt(0) ?
            samePattern(s1.substring(1), s2.substring(1))
            :
        false;
}
public static void main(String[] args) {
    String[] patterns = {
        "The*xamIs*y",    // true
        "Th*mIsEasy*",    // true
        "*",              // true
        "TheExamIsEasy",  // true
        "The*IsHard",     // false
    };
    for (String pattern : patterns) {
        System.out.println(samePattern("TheExamIsEasy", pattern));
    }
}

Алгоритм

По сути, вот рекурсивное определение:

  • Если s2 пусто, то samePattern, если s1 также пусто
  • В противном случае s2 не пусто
    • Если он начинается с *, то это samePattern, если
      • Это samePattern с удаленным *
      • Или это samePattern с персонажем, удаленным из s1 (если он есть)
    • В противном случае он начинается с обычного символа
      • Если он соответствует первому символу s1, то проверьте, равен ли он samePattern для остальных s1, s2
      • В противном случае это не samePattern, поэтому false

Упрощенная версия

Вот упрощенная версия вышеприведенного алгоритма: 

static boolean samePatternSimplified(String s1, String s2) {
    if (s2.length() == 0) {
        return s1.length() == 0;
    } else if (s2.charAt(0) == '*') {
        return samePatternSimplified(s1, s2.substring(1))
           || (s1.length() != 0 && samePatternSimplified(s1.substring(1), s2));
    } else if (s1.length() != 0 && s2.charAt(0) == s1.charAt(0)) {
        return samePatternSimplified(s1.substring(1), s2.substring(1));
    } else {
        return false;
    }
}

API ссылки

...