java - 不使用循环移动数组

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，如果 s1 按字典顺序小于 s2，则返回 -1，如果 s1 >s2，则返回 1。一些测试输出：

    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