859. Buddy Strings

Problem¶

Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

• For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Constraints:

• 1 <= s.length, goal.length <= 2 * 10**4
• s and goal consist of lowercase letters.

Solve¶

Read the problem¶

• Only one swap is allow, and we get two identical string

Analysis¶

• The constrain is really low
• There should be two case that return True, which is: 1. String s and goal have no different, we swap an identical character so the string remain unchanged; 2. String s and goal have a pair (x,y) being swap

Code it¶

• Just a regular loop through all character of pair(s, goal) check to find if there is any different character. Storing their position in diff array
• If len(s) > len(goal) or len(diff) != 0 and len(diff) != 2 then we can just return False
• For case 1. len(diff) == 0 we can loop through string s and find if any character is repeat (using set() to keep track which char have show up). Return True if found or False if not
• For case 2. len(diff) == 2 we can quick check if swapping 2 character with position diff[0], diff[1] of either s or goal is equal to the other one or not: Using s[diff[1]] == goal[diff[0]] and s[diff[0]] == goal[diff[1]]

Implement¶

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        # Find different of s and goal
        if len(s) != len(goal):
            return False

        diff = []
        for i, (x, y) in enumerate(zip(s, goal)):
            if x != y:
                diff.append(i)

        if len(diff) != 0 and len(diff) != 2:
            return False

        if len(diff) == 2:
            return s[diff[1]] == goal[diff[0]] and s[diff[0]] == goal[diff[1]]

        check = set()
        for c in s:
            if c not in check:
                check.add(c)
            else:
                return True
        return False