2

所以我试图弄清楚两个字符串组合在一起时是否是另一个字符串排列的子字符串。

我有一个我认为是可行的解决方案，但它在一些 JUnit 测试用例中失败了，我无法访问它失败的那些。

这是我的代码和一个测试用例

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()总是会返回最后一次比较的结果（这肯定不是你想要的）。

首先，您在对两个数组进行排序时做了正确的事情——这是一个经典的步骤，应该可以让您一次有效地评估它们。但是，您使用嵌套循环而不是单次循环——您打算在这里做什么？

单遍实现可能类似于：

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 回答
2

所以我们只关心两个组合字符串是否是另一个字符串排列的子集，这意味着长度实际上可以不同。所以假设我们有：

String a = "tommarvoloriddle";
String b = "lord";
String c = "voldemort";

char[] master = a.ToCharArray();
char[] combined = (b + c).ToCharArray();

Arrays.Sort(master);
Arrays.Sort(combined);

System.out.println(IsPermutation(master, combined) ? "YES" : "NO");

那么我们的方法是：

static boolean IsPermutation(char[] masterString, char[] combinedString)
{
    int combinedStringIndex = 0;
    int charsFound = 0;
    int result = 0;

    for (int i = 0; i < masterString.Length; ++i) {
        result = combinedString[combinedStringIndex].CompareTo(masterString[i]);
        if (result == 0) {
            charsFound++;
            combinedStringIndex++;
        }
        else if (result < 0) {
            return false;
        }
    }

    return (charsFound == combinedString.Length);
}

上述方法的作用：它开始比较两个字符串的字符。如果我们有一个不匹配，即当前索引处的字符与当前masterString索引处的字符不匹配combinedString，那么我们只需查看下一个字符，masterString看看是否匹配。最后，我们计算从 中匹配的字符总数combinedString，如果它们等于combinedString（其长度）中的字符总数，那么我们已经确定它确实是 的排列masterString。如果在任何时候，当前字符在masterString数值上大于当前字符，combinedString那么这意味着我们永远无法匹配当前字符，所以我们放弃了。希望有帮助。

于 2013-05-08T00:00:21.817 回答
0

如果两个字符串是另一个的排列，你应该能够做到这一点

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 回答