java - ループを使用せずに配列をシフトする

Question

再帰を使用して 2 つの文字列を同等にするように依頼されました。ループは絶対に許されません。私の考えは、要素ごとにチェックし、時間の経過とともに文字列を縮小することですが、それを実装する方法がわかりません。配列の要素をチェックしたら削除し、2 番目の要素が最初の要素になった配列から新しい文字列を作成します。

どうやってそれを行うのですか？

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. インデックスがいずれかの文字列の長さを超えているかどうかを確認します。同じ長さでなければならないことはすでに確認済みです。交差インデックスとは、各インデックスのすべての文字が 2 つの文字列で 1 対 1 で一致することを意味します。(手順 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