Блог

Мой учитель дал мне задание, в котором есть две строки, полное слово и подстрока, содержащая буквы, которые могут быть в полном слове. Цель состоит в том, чтобы использовать рекурсию, чтобы увидеть, содержит ли полное слово буквы подстроки в порядке их указания. вот несколько примеров того, о чем я говорю:

-«xd», «test» возвращает false, потому что одна или несколько букв подстроки не существуют в полном слове.

-«ts», «test» возвращает true, потому что обе буквы найдены в полном слове.

-«trl», «turtle» возвращает true, потому что все буквы найдены в полном слове и находятся в правильном порядке.

-«tlr», «turtle» возвращает false, потому что, хотя все буквы существуют в полном слове, они не были найдены в порядке подстроки.

Я пытался:

 public boolean contains_recursive(String partial, String full) {

    String[] partialArray = partial.split("");

    if(full.contains(partialArray[0])) {
        partialArray = Arrays.copyOfRange(partialArray, 1, partialArray.length);
        String newPartial = "";
        for(String character : partialArray) {
            System.out.println(character);
            newPartial  = character;
        }
        contains_recursive(newPartial, full);
    }

    return false;
}
  

но не знаю, куда идти оттуда. Спасибо за любую помощь.

Попробуйте это:

 public boolean containsRecursive(String partial, String full) {
  if (partial.isEmpty()) return true;
  if (full.isEmpty()) return false;

  int firstOccurrence = full.indexOf(partial.charAt(0));

  return firstOccurrence >= 0 amp;amp; containsRecursive(partial.substring(1), full.substring(firstOccurrence   1));
}
  

Объяснение:

 if (partial.isEmpty()) return true;
  

• Если в полной строке нечего искать, то технически «подстрока» существует (т. Е. пустая строка является подстрокой всех строк).

 if (full.isEmpty()) return false;
  

• Если мы дошли до этого момента, это означает, что в искомой нами частичной строке есть символы, но, к сожалению, в full строке нет символов для сравнения, поэтому эти символы в partial строке определенно не будут в full , return false .

 int firstOccurrence = full.indexOf(partial.charAt(0));
  

• Мы зашли так далеко, что оба partial и full не являются пустыми, давайте используем метод экземпляра String indexOf . Этот метод вернет местоположение первого вхождения данного символа или -1 , если символ не существует в строке.
• Мы используем partial.charAt(0) , потому что, если первый символ partial не существует в full , то почему мы должны проверять оставшиеся символы в partial ? Другими словами, давайте убедимся, что первый символ существует, прежде чем проверять остальные.

 return firstOccurrence >= 0 amp;amp; containsRecursive(partial.substring(1), full.substring(firstOccurrence   1));
  

• Мы проверяем, firstOccurrence >= 0 потому что, если firstOccurrence есть -1 , это означает, что partial первого символа не было в, full поэтому это должно вернуться false .
• amp;amp; используется для короткого замыкания. Другими словами, если firstOccurrence >= 0 есть false , вторая половина логической проверки (т. Е. рекурсивный вызов) не будет оценена, потому что false amp;amp; anyOtherBooleanExpression ==> false .
• Вторая половина логической проверки — это рекурсивный вызов. Мы заходим так далеко, только если первый символ partial находится в full . Теперь мы снова вызываем нашу функцию, беря все символы partial минус ее первый символ или partial.substring(1) .
• Поскольку firstOccurrence представляет собой первое местоположение первого символа partial в full , нас не волнуют (возможные) пропущенные местоположения.
  • Например, если partial = "mtr" и full = "computer" , m совпадают в позиции 2 , мы должны начать проверку partial = "tr" внутри full = "puter" при следующем рекурсивном вызове.

Надеюсь, это поможет!