检查两个字符串是否是变位词

Question

如果字符串 t 是 s 的变位词，我想 return 为真。我已经将s的所有字符压入栈中，并将t的每个字符与栈顶元素进行比较，如果字符匹配，则执行弹出操作。如果在最后，堆栈为空，这意味着字符串 t 是字符串 s 的变位词。这是我的代码 -

public boolean isAnagram(String s, String t) {
    char[] charArray1 = s.toCharArray();
    char[] charArray2 = t.toCharArray();
    if (s.length() != t.length())
    {
        return false;
    }
    Stack<Character> newStack = new Stack<Character>();
    for (int i=0; i<charArray1.length;i++)
    {
        newStack.push(charArray1[i]);
    }
    for (int j=0;j<charArray2.length;j++)
    {
        if(charArray2[j] == newStack.peek())
        {
            newStack.pop();
        }
    }
    if (newStack.isEmpty())
    {
        return true;
    }
    else
    return false;
}



error: s= "abc", t= "bac", Doesn't seem to declare these two strings as anagram

Answer 1

栈是这个问题的错误数据结构，因为peek()只看栈顶元素，但是你想检查charArray2中的每个字符是否都可以找到charArray1 中的任何地方。一种更简单的方法是对数组进行排序，然后将它们进行比较 Strings:

public boolean isAnagram(String s, String t) {
    char[] charArray1 = s.toCharArray();
    char[] charArray2 = t.toCharArray();
    Arrays.sort(charArray1);
    Arrays.sort(charArray2);
    String string1 = new String(charArray1);
    String string2 = new String(charArray2);
    return string1.contentEquals(string2);
}

Answer 2

无需显式使用堆栈。使用以下任一方法。

使用排序：

1) 对两个字符串进行排序
2）比较排序后的字符串

"Or"

计数字符并将其存储在数组中：

此方法假定两个字符串中的可能字符集很小。在下面的实现中，假设字符使用8位存储，可以有256个可能的字符。
1) 为两个字符串创建大小为 256 的计数数组。将计数数组中的所有值初始化为 0.
2) 遍历两个字符串的每个字符并增加相应计数数组中字符的计数。
3) 比较计数数组。如果两个计数数组相同，则 return 为真。

检查两个字符串是否是变位词

Check if two strings are anagram

algorithm

stack

anagram

array-algorithms

使用排序：

计数字符并将其存储在数组中：