题目
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
解法
如果将s和t进行排序，然后判断两个字符串是否一样
下面通过各种排序方法来解决，可以理解所有的排序方法
我们按照从小到大开始排序
冒泡
先找到最大的，然后放在倒数第一位；
再找次大的，放在倒数第二位；
再第三大的，放在倒数第三位；
以此类推
注意事项
假如字符串长度n，其实找到前n-1大的即可，因为剩下的那个肯定是最小值；
代码
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()){
return false;
}
char* p_s = (char*)s.c_str();
char* p_t = (char*)t.c_str();
buddleSort(p_s, s.size());
buddleSort(p_t, t.size());
printf("%s, %s\n", p_s, p_t);
for(int i=0;i<s.size();i++){
if(p_s[i] != p_t[i]){
return false;
}
}
return true;
}
void buddleSort(char* s, int s_len){
for(int i = 0;i<s_len-1;i++){
for(int j=0;j<s_len-1-i;j++){
if(s[j]>s[j+1]){
char tmp = s[j];
s[j] =s[j+1];
s[j+1]=tmp;
}
}
}
}
};
复杂度和稳定性
时间：O(n2)，因为循环遍历两次，所以n2
空间：O(1)，原地交换，没有使用额外的空间
稳定性：稳定的，因为如果两者相等，不会交换顺序
堆排序
将数组转成一个完全二叉树，一个节点的值比左右两个孩子都要大；
这样最大值就是根节点，去除根节点后，剩下的树就不符合堆的特性了，所以如果还能让第二大小的点移到根节点，那么就实现排序问题；
步骤
- 将被排序的数组行成一个完全二叉树
- 将该完全二叉树形成一个堆
- 排序，即陆续将根节点移除，并接着将剩下的二叉树形成一个堆
代码
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()){
return false;
}
char* p_s = (char*)s.c_str();
char* p_t = (char*)t.c_str();
heapSort(p_s, s.size());
heapSort(p_t, t.size());
printf("%s, %s\n", p_s, p_t);
for(int i=0;i<s.size();i++){
if(p_s[i] != p_t[i]){
return false;
}
}
return true;
}
void heapSort(char* s, int s_len){
//init heap
for(int i=s_len/2-1; i>=0; i--){
heapify(s, s_len, i);
}
//sort
while(s_len>0){
char tmp = s[0];
s[0] = s[s_len-1];
s[s_len-1]=tmp;
s_len--;
heapify(s, s_len, 0);
}
}
void heapify(char* s, int s_len, int i){
int max = i;
int left_child = i*2 +1;
int right_child = i*2 +2;
if(left_child<s_len && s[max] < s[left_child]){
max = left_child;
}
if(right_child<s_len && s[max] < s[right_child]){
max = right_child;
}
if(max != i){
char tmp = s[i];
s[i] = s[max];
s[max] = tmp;
heapify(s, s_len, max);
}
}
};
注意
假设数组长度是n，当前节点是i，那么
左孩子索引 1 * 2 +1;
右孩子索引 1 * 2 + 2;
父节点：(i-1)/2
最后一个叶子：n-1
最有一个非叶子节点：(n-1-1)/2=n/2-1
复杂度和稳定性
时间复杂度：O(nlgn)
稳定性：不稳定，因为通过调换，可能会将相等的两个次序打乱
快速排序
步骤
这是一个分治思想，先找一个中位数，然后小于中位数的全都放在左边，大于中位数的全都放在右边；
然后递归执行中位数左边和右边；
注意事项
中位数最好不要是最大值和最小值，因为如果是最大或者最小的话，会导致其实没有分治，这样复杂度和冒泡一样。
代码
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()){
return false;
}
char* p_s = (char*)s.c_str();
char* p_t = (char*)t.c_str();
quickSort(p_s, s.size());
quickSort(p_t, t.size());
printf("%s, %s\n", p_s, p_t);
for(int i=0;i<s.size();i++){
if(p_s[i] != p_t[i]){
return false;
}
}
return true;
}
int getPivot(char* s, int left, int right){
int middle = (left + right)/2;
if(s[left] < s[middle] && s[middle] < s[right]){
return middle;
}else if(s[left] > s[middle] && s[middle] > s[right]){
return middle;
}else if(s[middle] > s[left] && s[left] > s[right]){
return left;
}else if(s[middle] < s[left] && s[left] < s[right]){
return left;
}else if(s[middle] > s[right] && s[right] > s[left]){
return right;
}else if(s[middle] < s[right] && s[right] < s[left]){
return right;
}else{
return middle;
}
}
void quickSort(char* s, int begin, int end){
if(begin >= end){
return;
}
int pivot = getPivot(s, begin, end);
swap(s, pivot, begin);
pivot=begin;
int low = begin + 1;
int high = end;
bool high_to_low = true;
while(high>=low){
if(high_to_low){
if(s[high]<=s[pivot]){
swap(s, high, pivot);
pivot=high;
high_to_low=false;
}
high--;
}else{
if(s[low]>=s[pivot]){
swap(s, low, pivot);
pivot=low;
high_to_low=true;
}
low++;
}
}
quickSort(s, begin, pivot-1);
quickSort(s, pivot+1, end);
}
void quickSort(char* s, int s_len){
quickSort(s, 0, s_len-1);
}
void swap(char* s, int a, int b){
char tmp = s[a];
s[a] = s[b];
s[b]= tmp;
}
};
复杂度和稳定性
时间复杂度：O(nlgn)
稳定性：不稳定，因为通过调换，可能会将相等的两个次序打乱
计数排序
由于被排序的元素是小写字母，是26个，数量并不多，可以该问题可以使用计数排序，这样只要记下每个字母有多少，这样就能判断两个字符串是否一样
代码
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()){
return false;
}
char* p_s = (char*)s.c_str();
char* p_t = (char*)t.c_str();
countSort(p_s, s.size());
countSort(p_t, t.size());
printf("%s, %s\n", p_s, p_t);
for(int i=0;i<s.size();i++){
if(p_s[i] != p_t[i]){
return false;
}
}
return true;
}
void countSort(char* s, int s_len){
int alphas[26] = {0};
for(int i = 0; i < s_len; i++){
alphas[s[i] - 'a']++;
}
int index = 0;
for(int i = 0; i<26;i++){
for(int j=0;j<alphas[i];j++){
s[index] = i + 'a';
index++;
}
}
}
void swap(char* s, int a, int b){
char tmp = s[a];
s[a] = s[b];
s[b]= tmp;
}
};
复杂度和稳定性
时间复杂度：O(n)
空间复杂度：O(n)，空间换时间
稳定性：稳定，因为通过调换，可能会将相等的两个次序打乱
