[数据结构与算法]LeetCode—895.亲密字符串

leetcode对应题

此处有几个需要判断的点：

• 两个字符串长度不一致，返回false。例如：abcd和abc
• 两个字符串的字母出现不同次数不同，返回false。例如：abc和abd
• 在得知两个字符串的对应的字母个数相等，位置可能会不等，求出位置不等的个数有几个。如：abc和acb。如果有两个位置不同因此能够直接进行交换则为亲密字符串。若只有一个或者超过两个的字母位置不同，则肯定不是亲密字符串。如：abcd和abcb。或者abcde和acbed。
• 两字符串完全相同，判断是否存在某一字符出现两次以上，若存在，返回true。此处有可能返回false情况有ab和ab 。
• 需要注意的是这块代码能够求得每一个字母对应的个数：arr[s.charAt(i) - 'a']++;
• 时间复杂度：O(N)其中 N 为字符串的长度。我们至多遍历字符串两遍。空间复杂度：O（C）。需要常数个空间保存字符串的字符统计次数，我们统计所有小写字母的个数，因此C=26 。

class Solution {
    public boolean buddyStrings(String s, String goal) {
        // 长度一样
        int len1 = s.length();
        int len2 = goal.length();
        if(len1 != len2){
            return false;
        }

        // 字符出现的次数是否一样
        int[] arr1 = getArray(s);
        int[] arr2 = getArray(goal);

        for(int i = 0; i < 26; i++){
            if(arr1[i] != arr2[i]){
                return false;
            }
        }

        // 有几个位置不一样的
        int num = 0;
        for(int i = 0; i < len1; i++){
            if(s.charAt(i) != goal.charAt(i)){
                num++;
            }
        }
        
        if(num == 2){
            return true;
        }
        if(num == 1 || num > 2){
            return false;
        }

        // 如果都相等的话，看一下有没有重复可以直接交换的
        for(int i = 0; i < 26; i++){
            if(arr1[i] >= 2){
                return true;
            }
        }
        return false;
    }

    public int[] getArray(String s){
        int[] arr = new int[26];
        for(int i = 0; i < s.length(); i++){
            arr[s.charAt(i) - 'a']++;
        }
        return arr;
    }
}