3.1 LintCode211-字符串置换
bool Permutation(string &A, string &B){
解法一：单纯使用数组计数，缺点是对如果带有特殊符号的字符串是无法处理的
时间复杂度是O（n）
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int cnt1[26];
int cnt2[26];
bool Permutation(string &A, string &B) {
if (A.size() != B.size())
return false;
else {
for (int i = 0; i < A.size(); i++) {
cnt1[A[i] - 'a']++;
cnt2[B[i] - 'a']++;
}
}
for (int i = 0; i < 26; i++) {
if (cnt1[i] != cnt2[i])
return false;
}
return true;
}
int main() {
string a, b;
cin >> a >> b;
if (Permutation(a, b))
cout << "true";
else
cout << "false";
return 0;
}
解法二:使用排序 使用快速排序时间复杂度是O(nlogn)(这个是快排的时间复杂度)+O(n)（遍历的时间复杂度）=======O（nlogn） 对于第一种解法来说效率是更低的
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int cnt1[26];
int cnt2[26];
bool Permutation(string &A, string &B) {
if (A.size() != B.size())
return false;
else {
sort(A.begin(), A.end());
sort(B.begin(), B.end());
if (A == B)
return true;
else
return false;
}
}
int main() {
string a, b;
cin >> a >> b;
if (Permutation(a, b))
cout << "true";
else
cout << "false";
return 0;
}
解法三：使用hash数据结构（解决了时间的问题，也解决了字符串范围的问题，无论字符串其中是什么特殊字符都可解决） 时间复杂度为O（n）对于长度越长的字符串来说效率是越高的。
#include <iostream>
#include <unordered_map>
using namespace std
const int N = 1e5 + 10;
typedef unordered_map<char, int> mp;
mp map1;
mp map2;
//对于map的比较
bool cmp_map(mp map1, mp map2) {
if (map1.size() != map2.size())
return false;
auto it1 = map1.begin();
auto it2 = map2.begin();
for (; it1 != map1.end(); ++it1, ++it2) {
if (it1->first != it2->first || it1->second != it2->second)
return false;
}
return true;
}//这里是对于hash遍历的操作
bool Permutation(string &A, string &B) {
if (A.size() != B.size())
return false;
else
for (int i = 0; i < A.size(); i++) {
map1[A[i]]++;
map2[B[i]]++;
}
return cmp_map(map1, map2);
}
int main() {
string a, b;
cin >> a >> b;
if (Permutation(a, b))
cout << "true";
else
cout << "false";
return 0;
}
标签：return,string,int,置换,++,字符串,false,size From： https://www.cnblogs.com/FJCLJ/p/18161922