Смещение массивов без использования петель

Question

Меня попросили приравнять две строки, используя рекурсию. Абсолютно никакие петли не допускаются. Моя идея - проверить элемент по элементу, со временем сжимать строку, но я не знаю, как ее реализовать. Я хочу удалить элементы массива после проверки, а затем создать новую строку из массива, в котором второй элемент теперь первый, и так далее.

Как это сделать?

Answer 1

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

isMatching(str1, str2, index): 

    #check if they have same length, else return false at 1st call 
    if(len(str1) != len(str2)) 
    return false      #<-- termination step 

    #if index crossed the length, that means all char in strings are over 
    #we have already established that they have same length 
    if(index > len(str1)) 
    return true      #<-- termination step 

    #compare char by char 
    if(str1[index] == str2[index]) 
    isMatching(str1, str2, index+1) #<-- propagation step 
    else 
    return false      #<-- termination step 

это рекурсия начинается с индексом 1, предположение 1 индексирование строки. Выше всего это псевдо-код.

Вы видите, что рекурсия продолжает вызывать функцию до тех пор, пока не будет выполнен этап завершения, иначе она будет включать и выключать одну и ту же функцию с новым значением индекса для сравнения. Таким образом,

1. Посмотрите, если длина одинакова, если не возвращает false. Конец истории.

2. Посмотрите, если указатель пересек длину одной из строк. Поскольку мы уже убедились, что они должны иметь одинаковую длину. Пересечение индекса означает, что все символы в каждом индексе имеют взаимно однозначное совпадение в двух строках. (см. шаг 3).

3. Сравните характер указателя. Если это соответствует, продолжайте ... снова вызовите функцию, на этот раз попросите сравнить следующий индекс

4. Если индекс не совпал, у нас есть несоответствие, прекратите процесс. Строки не совпадают, возвращает false.

Answer 2

int compareStrings(String s1,String s2,int curIndex) 
{ 

    if(s1.length()==0 && s2.length()==0) return 0; // equal empty strings 
    if(s1.length()==0 && s2.length()>0) return -1; // s1 is empty, s1<s2 
    if(s1.length()>0 && s2.length()==0) return 1; // s2 is empty, s1>s2 

    if(s1.charAt(curIndex)<s2.charAt(curIndex)) return -1; 

    if(s1.charAt(curIndex)>s2.charAt(curIndex)) return 1; 

    if(curIndex+1<Math.min(s1.length(),s2.length())) 
    { 
     return compareStrings(s1, s2, curIndex+1); 
    } 
    else 
    { 
     if(s1.length()==s2.length()) return 0; 
     else if(s1.length()<s2.length()) return -1; 
     else return 1; 
    } 


} 

Функция compareStrings возвращает 0, если строки равны, -1, если s1 лексически меньше, чем s2, и 1, если s1> s2. Некоторые тестовые выходы:

System.out.println(compareStrings("test","test",0)); // 0 
    System.out.println(compareStrings("test","tesw",0)); // -1 
    System.out.println(compareStrings("tesw","test",0)); // 1 
    System.out.println(compareStrings("tesw","tes",0)); //1 
    System.out.println(compareStrings("tes","tesw",0)); //-1