By Long Luo
Leetcode 859. 亲密字符串。
方法一:模拟
思路与算法:
虽然这个题目很简单,根据题意,但需要考虑一些边界情况:
- 如果字符串长度不一致,很明显不是亲密字符串;
- 如果字符串长度len<2,不是亲密字符串;
- 如果两个字符串一摸一样,但是必须更换位置,此时合法的情况只能交换两个一样的字母,意味着有字母至少出现两次;
- 一般情况,我们找到两个字符串字符不同的位置,但不能多于两个,同时他们可以互换。
那么针对这两种情况:
-
字符串不相同:遍历比较两个串,记录下不同的位置,判断这两个位置是不是正好满足互换关系即可。如果有超过两个不同的位置可以直接返回false。
-
字符串相同:遍历字符串,对每个字母计数;如果两个串没有不同的地方,必须有字母在字符串中出现不止一次。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| public boolean buddyStrings(String s, String goal) { if (s == null || goal == null || s.length() <= 1 || goal.length() <= 1 || s.length() != goal.length()) { return false; }
int len = s.length(); int first = -1; int second = -1; if (s.equals(goal)) { int[] count = new int[26]; for (int i = 0; i < len; i++) { count[s.charAt(i) - 'a']++; if (count[s.charAt(i) - 'a'] > 1) { return true; } } return false; } else { for (int i = 0; i < len; i++) { if (s.charAt(i) != goal.charAt(i)) { if (first == -1) { first = i; } else if (second == -1) { second = i; } else { return false; } } } }
if (first != second && first >= 0 && second >= 0 && s.charAt(first) == goal.charAt(second) && s.charAt(second) == goal.charAt(first)) { return true; }
return false; }
|
也可以另外一种写法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| bool buddyStrings(string s, string goal) { int lenSrc = s.length(); int lenGoal = goal.length(); if (lenSrc != lenGoal || lenSrc <= 1) { return false; }
vector<char> cntSrc(26); vector<char> cntGoal(26); int diffCnt = 0; for (int i = 0; i < lenSrc; i++) { int chSrc = s.at(i) - 'a'; int chGoal = goal.at(i) - 'a'; cntSrc[chSrc]++; cntGoal[chGoal]++; if (chSrc != chGoal) { diffCnt++; } }
bool isSame = false; for (int i = 0; i < 26; i++) { if (cntSrc[i] != cntGoal[i]) { return false; }
if (cntSrc[i] > 1) { isSame = true; } }
return diffCnt == 2 || (diffCnt == 0 && isSame); }
|
复杂度分析
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗