2

したがって、2 つの文字列を組み合わせたときに別の文字列の順列の部分文字列であるかどうかを調べようとしています。

私は実用的なソリューションであると信じているものを持っていますが、JUnit テスト ケースの一部に失敗しており、失敗しているテスト ケースにアクセスできません。

これが1つのテストケースを含む私のコードです

String a="tommarvoloriddle";
String b="lord";
String c="voldemort";
String b= b+c; 
char[] w= a.toCharArray();
char[] k= b.toCharArray();
Arrays.sort(k);
Arrays.sort(w);
pw.println(isPermuation(w,k)?"YES":"NO");


static boolean isPermuation(char[] w, char[] k)
{
    boolean found=false;
    for(int i=0; i<k.length; i++)
    {
        for(int j=i; j<w.length; j++)
        {
            if(k[i]==w[j])
            {
                j=w.length;
                found=true;
            }
            else
                found=false;
        }
    }


    return found;
}

これが常に正しい答えを生成するのを助けるのは素晴らしいことであり、それをより効率的にするのにも役立つでしょう

4

3 に答える 3

3

あなたが持っているものは実用的な解決策ではありません。ただし、なぜそうなると思ったのかを説明していないため、意図したことを理解するのは困難です。foundあなたのコードは内部ループごとに無条件に更新されるため、isPermutation()常に最後の比較の結果が返されることを指摘します(これは確かにあなたが望むものではありません)。

最初に 2 つの配列を並べ替えるという正しいことを行いました。これは、1 つのパスでそれらを効率的に評価できるようにするための古典的な手順です。しかし、1 回のパスの代わりに、入れ子になったループを使用します。ここで何を意図したのでしょうか。

シングル パスの実装は次のようになります。

static boolean isPermutation(char[] w, char[] k) {
  int k_idx=0;
  for(w_idx=0; w_idx < w.length; ++w_idx) {
    if(k_idx == k.length)
      return true; // all characters in k are present in w
    if( w[w_idx] > k[k_idx] )
      return false;  // found character in k not present in w
    if( w[w_idx] == k[k_idx] )
      ++k_idx;  // character from k corresponds to character from w
  }
  // any remaining characters in k are not present in w
  return k_idx == k.length;
}
于 2013-05-08T00:19:05.790 に答える
0

2 つの文字列が他の文字列の順列である場合、これを行うことができるはずです

public static boolean isPermuted(Strign s1, String s2) {
     if (s1.length() != s2.length()) return false;

     char[] chars1 = s1.toCharArray();
     char[] chars2 = s2.toCharArray();
     Arrays.sort(chars1);
     Arrays.sort(chars2);
     return Arrays.equals(chars1, chars2);
}

これは、並べ替えたときに文字が同じで、同じ数であることを意味します。

于 2013-05-08T05:27:13.897 に答える