【每日挠头算法题(1)】——旋转字符串|亲密字符串

---

一、旋转字符串

点我直达终点~

思路1

前提：如果s串和goal串长度不等，则goal串不可能是s串旋转得来，直接返回false；

通过观察，可以发现每旋转一次，第一个字符就会出现在最后一个字符的位置处，其余字符均往前挪动一个位置。

所以我们首先将第一个字符保存，然后挪动其他字符，再将保存的字符放到最后。

其次判断s和goal是否相等，如果不等，则继续按照上述方式旋转

注意:如果旋转s的长度次后，与goal仍然不想等，返回false

代码:

class Solution {
public:bool rotateString(string s, string goal) {if(s.size()!=goal.size())return false;for(int j = 0 ; j <s.size();++j){char ch = s[0];//旋转一遍for(int i = 1;i <s.size();++i){s[i-1] = s[i];}s[s.size()-1] = ch;if(s == goal){return true;}}//如果旋转完s.size()遍，还不是true，那就falsereturn false;}
};

时间复杂度：O(N^2) 空间复杂度：O(1)(原地旋转)

思路2

前提：如果s串和goal串长度不等，则goal串不可能是s串旋转得来，直接返回false；

一个巧妙的解法：运用如果goal串由s串旋转得来，那么goal串一定是s+s串的子串。
只需要判断goal字符串是否为s+s串的子串即可。

class Solution 
{
public:bool rotateString(string s, string goal){string ss = s+s;if(s.size() == goal.size() && ss.find(goal) != string::npos)return true;return false;}
};

时间复杂度：O(N) 空间复杂度O(N)

二、亲密字符串

点我直达终点~

思路

前提：如果s串和goal串长度不等，则goal串不可能是s串旋转得来，直接返回false；

对于这道题，首先遍历一遍s串，一边遍历一边与goal字符串进行对比，如果对应下标的goal串的字符和s串的对应下标的字符不相等，则记录不等的字符和下标。（s串和goal串一定只有两个不相等的字符）

找到后，如果pos1下标和pos2下标相同，说明s串和goal串一定相等。
然而这里存在两种情况，如题目描述：
情况1：ab和ab
情况2：aa和aa
此时我们不需要分情况讨论，只需要找到s字符串的任意一个字符如果出现两次及以上，则说明交换s字符串的任意两个相同的字符一定与goal字符串相等。
比如: aabab 和aabab，s字符串中的a出现了三次，b出现了两次，
那么无论怎么交换其中的a或者b，s字符串始终和goal字符串相等。

如果字符串pos1下标和pos2下标不同，则交换对应的pos1和pos2的字符，再判断是否与goal串相等即可。

详细请看代码：

class Solution {
public:bool buddyStrings(string s, string goal) {   //1.长度不等，必然不是亲密字符串if(s.size()!=goal.size())return false;char arr[2];//找第一个不相同的字符,并记录下标int i = 0;int pos1 = 0,pos2 = 0;for(; i<s.size();++i){if(s[i]!=goal[i]){arr[0] = s[i];pos1 = i;break;}}//找第二个不相同的字符for(i+=1; i<s.size();++i){if(s[i]!=goal[i]){arr[1] = s[i];pos2 = i;break;}}//  如果pos1 == pos2,说明s和goal是完全相等的两个串//此时有两种情况，如果s中有两个位置交换后还是原来的s，此时s和goal相等。//但不管是哪种情况，我们都只需要找出任意一个字符出现2次及以上就可以知道是亲密字符串if(pos1 == pos2){vector<int> count(26);for(int i = 0;i<s.size();++i){count[s[i] - 'a']++;if(count[s[i] - 'a']>=2)return true;}return false;}//此种情况不是s串和goal串相等，那么正常交换两个字符的位置然后判断是否与goal相等即可。else{swap(s[pos1],s[pos2]);if(s == goal)return true;return false;}}
};

时间复杂度：O(N)； 空间复杂度O(1) 只消耗常量个空间，即26

---

总结

通过这两道题，学习到了旋转字符串的一般规律是转化为找子串的问题；
而亲密字符串的本质就是分情况讨论

情况1：如果s!=goal
情况2：如果s==goal

的分别处理方式。