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

Question

问题是给定两个字符串，检查给定的两个字符串是否 anagram 彼此。字符串的变位词是包含相同字符的另一个字符串，只是字符的顺序可以不同。例如，“act”和“tac”是彼此的变位词。

输入：输入的第一行包含一个整数 T，表示测试用例的数量。每个测试用例仅包含 'lowercase' 中的两个字符串，在一行中。

输出：如果两个字符串是变位词则打印不带引号的 "YES" 否则打印 "NO".

约束条件： 1≤T≤30 1 ≤ |s| ≤ 10^16

示例：输入： 1个过敏过敏

输出：否

我的方法是首先检查字符串的长度，如果它们不相等则简单地打印出 NO 如果它们相等则对字符串进行排序然后比较元素.

我在一些简单的输入上得到了正确的输出，但在复杂的输入上却没有，因为我的代码无法通过所有测试cases.I我无法找出我的错误。

#include <iostream>
using namespace std;
#include<string>
#include<algorithm>
int main() {
    int n, t=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string a,b;
        cin>>a>>b;
        cout<<"\n";
        if(a.length()!=b.length())
        {
            cout<<"NO";
        }
        else
        {
            sort(a.begin(),a.end());
            sort(b.begin(),b.end());
            for(int i=0;i<a.length();i++)
            {
                if(a[i]!=b[i])
                {
                    cout<<"NO";
                    break;
                }
                t++;
            }
           if(t==a.length())
           {
               cout<<"YES";
           }
        }
    }

    return 0;
}

Answer 1

你的代码似乎只给出了 1 个响应，而预期是 2 个。问题是你没有重置你的 t 变量 ;) 所以它总是递增的。运行示例：https://ideone.com/IYK6Ad

输入测试：

2
aab baa
a a

输出：

YES

固定码：

#include <iostream>
using namespace std;
#include<string>
#include<algorithm>
int main() {
    int n, t=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string a,b;
        cin>>a>>b;
        if(a.length()!=b.length())
        {
            cout<<"NO\n";
        }
        else
        {
            sort(a.begin(),a.end());
            sort(b.begin(),b.end());
            if(a != b)
            {
                cout<<"NO\n";
            }
            else
            {
                cout<<"YES\n";
            }
        }
    }

    return 0;
}

Example run

关于改进该算法的一些提示。现在我们只考虑 1 个测试用例来检查 anagram。

所以在你的情况下你有 2 * O(n * log n) complexity 主要是因为 std::sort（检查复杂性）

检查不同的大小是某种特殊情况。快速获胜。所以你可以保留它，但测试程序可能不会使用那些 ;)

是否通过当然会影响测试用例的大小和测试用例的数量。

改进思路：

计算每个字符（我们可以使用 std::map<char,int> 但是访问 map 中的元素也需要一些时间。所以在我们的例子中，我们对输入数据有所了解，因此我们可以从中受益。它应该是 ASCII数据，以便我们可以放入固定数组。）
如果特定字符的计数不同，我们知道答案！

对于这样的解决方案，我们将得到 O(n+m) + O(min(n,m))，其中 n 是字符串 a 的长度，m 是 b 的长度。更好的复杂性。

示例：

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin>>n;
    std::vector<int> aCountOfChars(256, 0);
    std::vector<int> bCountOfChars(256, 0);

    for(int i=0;i<n;i++)
    {
        string a,b;
        cin>>a>>b;
        std::vector<int> aCountOfChars(256, 0);
        std::vector<int> bCountOfChars(256, 0);

        for(int i=0;i<a.size();++i)
        {
            ++aCountOfChars[a[i]];  
        }
        for(int i=0;i<b.size();++i)
        {
            ++bCountOfChars[b[i]];  
        }

        if(aCountOfChars == bCountOfChars)
        {
            cout<<"YES\n";
        }
        else
        {
            cout<<"NO\n";
        }
    }
    return 0;
}

Run me

一些要检查的测试用例：

7
a b
aab baa
a a
aaaaaaaaaaaaaaaaaaaaaaaaaaaaa b
aabba bbaaa
act tac
allergy allergic

Nice article about such problem

Answer 2

static boolean isAnagram(String A, String B) {
       A=A.toLowerCase();
       B=B.toLowerCase();
       boolean f = false;
      char[] c = A.toCharArray();
      Arrays.sort(c);
      char[] d = B.toCharArray();
      Arrays.sort(d);
      String a = new String (c);
      String b = new String (d);
      if (a.equals(b)) {
          f=true;
      }
      return f;

   }

在Java编程语言中检查字谜的示例函数。

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

Checking if two strings are anagram

c++

string

algorithm

anagram