Java

  • /**
    
     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:
    
     0 <= A.length <= 20000
     0 <= B.length <= 20000
     A and B consist only of lowercase letters.
    
     */
    public class Buddy_Strings {
        class Solution {
            public boolean buddyStrings(String A, String B) {
                if (A == null || B == null) {
                    return false;
                }
                if (A.length() != B.length()) {
                    return false;
                }
    
                if (A.equals(B)) {
                    int[] count = new int[26];
                    for (int i = 0; i < A.length(); ++i)
                        count[A.charAt(i) - 'a']++;
    
                    for (int c: count) {
                        if (c > 1) {
                            return true;
                        }
                    }
                    return false;
                }
    
                // abcd, badc => false
                int p1 = -1;
                int p2 = -1;
    
                for (int i = 0; i < A.length(); i++) {
                    if (A.charAt(i) != B.charAt(i)) {
                        // record this position
                        if (p1 < 0) {
                            p1 = i;
                        } else if (p2 < 0) {
                            p2 = i;
                        } else {
                            return false; // found the 2 positions, for abcd and badc, also need to check the rest strings
    
                        }
                    }
                }
    
                if (p1 < 0 | p2 < 0) {
                    return false;
                }
    
                return A.charAt(p1) == B.charAt(p2) && A.charAt(p2) == B.charAt(p1) && A.substring(p2 + 1).equals(B.substring(p2 + 1));
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/buddy-strings/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        bool buddyStrings(string A, string B) {
            if (A.size() != B.size()) return false;
            int cnts[26] = {0}, first = -1, second = -1;
            bool hasDup = false;
            for (int i = 0; i < A.size(); ++i) {
                if (++cnts[A[i] - 'a'] == 2) hasDup = true;
                if (A[i] == B[i]) continue;
                if (first == -1) first = i;
                else if (second == -1) second = i;
                else return false;
            }
            return (first != -1 && second != -1 && A[first] == B[second] && A[second] == B[first])
                || (first == -1 && second == -1 && hasDup);
        }
    };
    
  • class Solution:
        def buddyStrings(self, A, B):
            """
            :type A: str
            :type B: str
            :rtype: bool
            """
            if len(A) != len(B):
                return False
            diff = 0
            idxs = []
            for i, a in enumerate(A):
                if B[i] != a:
                    diff += 1
                    idxs.append(i)
            counter = dict()
            if diff == 0:
                for a in A:
                    if a in counter and counter[a]:
                        return True
                    else:
                        counter[a] = True
            if diff != 2:
                return False
            return A[idxs[0]] == B[idxs[1]] and A[idxs[1]] == B[idxs[0]]
    

Java

  • class Solution {
        public boolean buddyStrings(String A, String B) {
            if (A == null || B == null || A.length() != B.length())
                return false;
            if (A.equals(B)) {
                char[] array = A.toCharArray();
                Arrays.sort(array);
                int length = array.length;
                for (int i = 1; i < length; i++) {
                    if (array[i] == array[i - 1])
                        return true;
                }
                return false;
            }
            List<Integer> differentIndices = new ArrayList<Integer>();
            int length = A.length();
            for (int i = 0; i < length; i++) {
                char cA = A.charAt(i), cB = B.charAt(i);
                if (cA != cB)
                    differentIndices.add(i);
            }
            if (differentIndices.size() != 2)
                return false;
            int index1 = differentIndices.get(0), index2 = differentIndices.get(1);
            return A.charAt(index1) == B.charAt(index2) && A.charAt(index2) == B.charAt(index1);
        }
    }
    
  • // OJ: https://leetcode.com/problems/buddy-strings/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        bool buddyStrings(string A, string B) {
            if (A.size() != B.size()) return false;
            int cnts[26] = {0}, first = -1, second = -1;
            bool hasDup = false;
            for (int i = 0; i < A.size(); ++i) {
                if (++cnts[A[i] - 'a'] == 2) hasDup = true;
                if (A[i] == B[i]) continue;
                if (first == -1) first = i;
                else if (second == -1) second = i;
                else return false;
            }
            return (first != -1 && second != -1 && A[first] == B[second] && A[second] == B[first])
                || (first == -1 && second == -1 && hasDup);
        }
    };
    
  • class Solution:
        def buddyStrings(self, A, B):
            """
            :type A: str
            :type B: str
            :rtype: bool
            """
            if len(A) != len(B):
                return False
            diff = 0
            idxs = []
            for i, a in enumerate(A):
                if B[i] != a:
                    diff += 1
                    idxs.append(i)
            counter = dict()
            if diff == 0:
                for a in A:
                    if a in counter and counter[a]:
                        return True
                    else:
                        counter[a] = True
            if diff != 2:
                return False
            return A[idxs[0]] == B[idxs[1]] and A[idxs[1]] == B[idxs[0]]
    

All Problems

All Solutions