leetcode每日一题-859:亲密字符串
链接
亲密字符串
题目
分析
题目本身不是很难,但是有不少需要注意的地方,逐一来进行分析。首先如果两个字符串不一样长,那么肯定是false
。然后考虑长度相等的情况,如果s和goal刚开始就一样答案是什么呢?如果是类似于ab
,ab
这种类型的,那么也是false
,因为这种交换之后一定就不相等了;如果是aa
和aa
这种,在一些对应位置有相同的元素,那么交换后是true
。在来考虑值不相等的情况,首先从前往后遍历找到第一个不一样的位置下标,然后从后往前遍历找到最后一个不一样的。假设两个字符串只有一个位置不一样,那么答案一定是false
,如果两个位置不一样的话,交换这两个位置的字符,然后根据交换的s和goal值进行判断即可。
代码
C++
class Solution {
public:
unordered_map<char, int> m;
bool buddyStrings(string s, string goal) {
if(s.size() != goal.size()) return false;
int idx1 = -1, idx2 = -1;
for(int i=0 ; i<s.size() ; i++)
{
if(s[i] == goal[i])
m[s[i]] += 1;
}
for(int i=0 ; i<s.size() ; i++)
{
if(s[i] != goal[i])
{
idx1 = i;
break;
}
}
for(int i=s.size()-1 ; i>=0 ; i--)
{
if(s[i] != goal[i])
{
idx2 = i;
break;
}
}
if(idx1 != idx2 and idx1 != -1 and idx2 != -1)
{
swap(s[idx1], s[idx2]);
return s == goal;
}
if(idx1 == idx2 and idx2 != -1) return false;
for(auto ve : m)
{
if(ve.second > 1) return true;
}
return false;
}
};
Java
class Solution {
public boolean buddyStrings(String s, String goal) {
if (s.length() != goal.length()) {
return false;
}
if (s.equals(goal)) {
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
if (count[s.charAt(i) - 'a'] > 1) {
return true;
}
}
return false;
} else {
int first = -1, second = -1;
for (int i = 0; i < goal.length(); i++) {
if (s.charAt(i) != goal.charAt(i)) {
if (first == -1)
first = i;
else if (second == -1)
second = i;
else
return false;
}
}
return (second != -1 && s.charAt(first) == goal.charAt(second) &&
s.charAt(second) == goal.charAt(first));
}
}
}
作者:LeetCode-Solution