859. Buddy Strings

Problem:
Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.

Example 1:
Input: A = "ab", B = "ba"
Output: true
Example 2:
Input: A = "ab", B = "ab"
Output: false
Example 3:
Input: A = "aa", B = "aa"
Output: true
Example 4:
Input: A = "aaaaaaabc", B = "aaaaaaacb"
Output: true
Example 5:
Input: A = "", B = "aa"
Output: false
Analysis:
Buddy string qualifies the following conditoin:
1. Length equal
2. If exact equal, A must have duplicate, since swap is required.
3. A and B only have 2 chars diff, and these 2 chars can swap.
Solution:

class Solution {
    public boolean buddyStrings(String A, String B) {
        // compare length
        if (A.length() != B.length())
            return false;
        // equals, find duplicates
        if (A.equals(B)) {
            Set<Character> set = new HashSet<>();
            for (char c: A.toCharArray()) {
                set.add(c);
            }
            return set.size() != A.length();
        }
        // not equals
        List<Integer> diff = new ArrayList<>();
        for (int i = 0; i < A.length(); i++) {
            if (A.charAt(i) != B.charAt(i)) 
                diff.add(i);
        }
        
        return diff.size() == 2 && A.charAt(diff.get(0)) == B.charAt(diff.get(1)) 
            && A.charAt(diff.get(1)) == B.charAt(diff.get(0)); 
    }
}

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array