Sunday, March 10, 2019

Leetcode 859. Buddy Strings

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

Note:
  1. 0 <= A.length <= 20000
  2. 0 <= B.length <= 20000
  3. A and B consist only of lowercase letters.

Code (Java):
class Solution {
    public boolean buddyStrings(String A, String B) {
        if (A.length() != B.length() || A.length() < 2 || B.length() < 2) {
            return false;
        }
        
        // case 1: if A == B, we only need to replace the same characters
        //
        if (A.equals(B)) {
            int[] counts = new int[26];
            for (char c : A.toCharArray()) {
                counts[c - 'a']++;
                if (counts[c - 'a'] > 1) {
                    return true;
                }
            }
            
            return false;
        }
        
        // case 2: otherwise, we only swap once
        //
        int first = -1;
        int second = -1;
        for (int i = 0; i < A.length(); i++) {
            if (A.charAt(i) != B.charAt(i)) {
                if (first == -1) {
                    first = i;
                } else {
                    second = i;
                }
            }
        }
        
        return A.charAt(first) == B.charAt(second) && A.charAt(second) == B.charAt(first);
    }
}

No comments:

Post a Comment