Question

1790. Check if One String Swap Can Make Strings Equal

中文文档

Description

You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return true _if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings. _Otherwise, return false.

 

Example 1:

Input: s1 = "bank", s2 = "kanb"
Output: true
Explanation: For example, swap the first character with the last character of s2 to make "bank".

Example 2:

Input: s1 = "attack", s2 = "defend"
Output: false
Explanation: It is impossible to make them equal with one string swap.

Example 3:

Input: s1 = "kelb", s2 = "kelb"
Output: true
Explanation: The two strings are already equal, so no string swap operation is required.

 

Constraints:

• 1 <= s1.length, s2.length <= 100
• s1.length == s2.length
• s1 and s2 consist of only lowercase English letters.

Solutions

Solution 1: Counting

We use a variable $cnt$ to record the number of characters at the same position in the two strings that are different. If the two strings meet the requirements of the problem, then $cnt$ must be $0$ or $2$. We also use two character variables $c1$ and $c2$ to record the characters that are different at the same position in the two strings.

While traversing the two strings simultaneously, for two characters $a$ and $b$ at the same position, if $a \ne b$, then $cnt$ is incremented by $1$. If at this time $cnt$ is greater than $2$, or $cnt$ is $2$ and $a \ne c2$ or $b \ne c1$, then we directly return false. Note to record $c1$ and $c2$.

At the end of the traversal, if $cnt \neq 1$, return true.

The time complexity is $O(n)$, where $n$ is the length of the string. The space complexity is $O(1)$.

class Solution:
  def areAlmostEqual(self, s1: str, s2: str) -> bool:
    cnt = 0
    c1 = c2 = None
    for a, b in zip(s1, s2):
      if a != b:
        cnt += 1
        if cnt > 2 or (cnt == 2 and (a != c2 or b != c1)):
          return False
        c1, c2 = a, b
    return cnt != 1

class Solution {
  public boolean areAlmostEqual(String s1, String s2) {
    int cnt = 0;
    char c1 = 0, c2 = 0;
    for (int i = 0; i < s1.length(); ++i) {
      char a = s1.charAt(i), b = s2.charAt(i);
      if (a != b) {
        if (++cnt > 2 || (cnt == 2 && (a != c2 || b != c1))) {
          return false;
        }
        c1 = a;
        c2 = b;
      }
    }
    return cnt != 1;
  }
}

class Solution {
public:
  bool areAlmostEqual(string s1, string s2) {
    int cnt = 0;
    char c1 = 0, c2 = 0;
    for (int i = 0; i < s1.size(); ++i) {
      char a = s1[i], b = s2[i];
      if (a != b) {
        if (++cnt > 2 || (cnt == 2 && (a != c2 || b != c1))) {
          return false;
        }
        c1 = a, c2 = b;
      }
    }
    return cnt != 1;
  }
};

func areAlmostEqual(s1 string, s2 string) bool {
  cnt := 0
  var c1, c2 byte
  for i := range s1 {
    a, b := s1[i], s2[i]
    if a != b {
      cnt++
      if cnt > 2 || (cnt == 2 && (a != c2 || b != c1)) {
        return false
      }
      c1, c2 = a, b
    }
  }
  return cnt != 1
}

function areAlmostEqual(s1: string, s2: string): boolean {
  let c1, c2;
  let cnt = 0;
  for (let i = 0; i < s1.length; ++i) {
    const a = s1.charAt(i);
    const b = s2.charAt(i);
    if (a != b) {
      if (++cnt > 2 || (cnt == 2 && (a != c2 || b != c1))) {
        return false;
      }
      c1 = a;
      c2 = b;
    }
  }
  return cnt != 1;
}

impl Solution {
  pub fn are_almost_equal(s1: String, s2: String) -> bool {
    if s1 == s2 {
      return true;
    }
    let (s1, s2) = (s1.as_bytes(), s2.as_bytes());
    let mut idxs = vec![];
    for i in 0..s1.len() {
      if s1[i] != s2[i] {
        idxs.push(i);
      }
    }
    if idxs.len() != 2 {
      return false;
    }
    s1[idxs[0]] == s2[idxs[1]] && s2[idxs[0]] == s1[idxs[1]]
  }
}

bool areAlmostEqual(char* s1, char* s2) {
  int n = strlen(s1);
  int i1 = -1;
  int i2 = -1;
  for (int i = 0; i < n; i++) {
    if (s1[i] != s2[i]) {
      if (i1 == -1) {
        i1 = i;
      } else if (i2 == -1) {
        i2 = i;
      } else {
        return 0;
      }
    }
  }
  if (i1 == -1 && i2 == -1) {
    return 1;
  }
  if (i1 == -1 || i2 == -1) {
    return 0;
  }
  return s1[i1] == s2[i2] && s1[i2] == s2[i1];
}