[数据结构与算法]leetcode每日一题-859:亲密字符串

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