метод indexOf с использованием рекурсии

Question

Мне нужно написать рекурсивный метод indexOf, который принимает два параметра Strings as и возвращает начальный индекс первого вхождения второй строки внутри первой строки (или -1, если не найден). Я должен решить эту проблему, используя рекурсию. Вот некоторые примеры результатов:

indexOf("Barack Obama", "Bar") 0 

indexOf("Barack Obama", "ck") 4 

indexOf("Barack Obama", "a") 1 

indexOf("Barack Obama", "McCain") -1 

indexOf("Barack Obama", "BAR") -1 

Это мое решение, но это дает мне 6 для IndexOf («Барак Обама», «Маккейн») вместо -1.

public static int indexOf(String s1, String s2) { 
     if(s1.equals(s2)) 
      return 0; 

     else 
      return indexOfHelper(s1, s2, 0); 
    } 
private static int indexOfHelper(String s1, String s2, int ctr) { 
     if(s2.length() > s1.length()) 
      return -1; 

     if(s2.length() == 0 || s1.length() == 0) //base case 
      return ctr;  

     else     //recursive case 
      if(s1.charAt(0) == s2.charAt(0)){  //if there is a matching character 
       if(s1.substring(0, s2.length()).equals(s2)) 
        return ctr;  //if there is a matching character and the rest of the strings match as well 
       else 
        return -1;  //if there is a matching character but the rest of the strings don't match 
      } 
      else 
       return 1 + indexOfHelper(s1.substring(1), s2, ctr); 

}

Answer 1

Я должен сказать, что рекурсивный шаг был довольно сложно. Он проходит все тестовые примеры. Надеюсь, что после этого поможет. Java и C++ код здесь

код JAVA

int indexOf (String s1, String s2) { 

    if (s1.length() == 0 && s2.length() == 0) { 
     return 0; 
    } else if (s1.length() == 0) { 
     return -1; 
    } else if (s2.length() == 0) { 
     return 0; 
    } else if (s2.length()>s1.length()) { 
     return -1; 
    } 
    else if (s1.charAt(0) == s2.charAt(0)) { 
     int subIndex = indexOf(s1.substring(1),s2.substring(1)); 
     return subIndex == -1 ? -1: subIndex; 


    } else { 
     int subIndex = indexOf(s1.substring(1),s2); 
     return subIndex == -1 ? -1: subIndex+1; 
    } 

} 

C++ здесь

int indexOf (string s1, string s2) { 

     if (s1 == "" && s2 == "") { 
      return 0; 
     } else if (s1 == "") { 
      return -1; 
     } else if (s2=="") { 
      return 0; 
     } else if (s2.size()>s1.size()) { 
      return -1; 
     } 
     else if (s1 [0] == s2[0]) { 
      int subIndex = indexOf(s1.substr(1,s1.length()),s2.substr(1,s2.length())); 
      return subIndex == -1 ? -1: subIndex; 


     } else { 
      int subIndex = indexOf(s1.substr(1,s1.length()),s2); 
      return subIndex == -1 ? -1: subIndex+1; 
     } 

    } 

Answer 2

Вот мое решение

public static void main(String[] args) { 
    System.out.println(indexOf("Ninja!", "i")); 
    System.out.println(indexOf("ninja2", "ja2")); 
    System.out.println(indexOf("ninja2", "hae")); 
} 

public static int indexOf(String s, String contains) { 
    if (contains.length() > s.length()) { 
     return -1; 
    } 
    return indexOf(s, contains, 0); 
} 

private static int indexOf(String s, String contains, int index) { 
    if ((s.length() - contains.length()) < index) { 
     return -1; 
    } 
    if (s.substring(index, index + contains.length()).equals(contains)) { 
     return index; 
    } else { 
    return indexOf(s, contains, index + 1); 
    } 
}