[LeetCode] - 1790. Check if One String Swap can Make Strings Equal

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Check if One String Swap can Make Strings Equal" 문제입니다.

--> https://leetcode.com/problems/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.

---

class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        if (s1.equals(s2)) return true;
        int[] alpha = new int[s1.length()];
        int one = -100;
        int two = -100;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                if (one == -100 && two == -100) {
                    one = s1.charAt(i) - 'a';
                    two = s2.charAt(i) - 'a';
                } else {
                    one -= s2.charAt(i) - 'a';
                    two -= s1.charAt(i) - 'a';
                }
            }
        }
        return one == 0 && two == 0;
    }
}

 

이 코드는 주어진 두 문자열 s1과 s2가 같은 길이를 가지고 있을 때, 하나의 문자열에서 최대 한 번의 스왑으로 두 문자열이 같아질 수 있는지 여부를 확인합니다.

1. 문자열 동일 여부 확인 :
   • 두 문자열이 이미 동일하면 스왑이 필요 없으므로 true를 반환합니다.
2. 서로 다른 문자의 위치 및 값 추적 :
   • 두 문자열을 순회하며 서로 다른 문자가 있는 위치를 찾습니다.
   • one과 two 변수를 사용하여 서로 다른 문자의 값을 추적합니다.
   • 서로 다른 문자가 처음 발견되면 one과 two에 각각 s1과 s2의 해당 문자의 값을 저장합니다.
   • 두 번째로 다른 문자가 발견되면 one에서 s2의 문자를 빼고, two에서 s1의 문자를 뺍니다.
3. 스왑 가능성 확인 :
   • one과 two가 모두 0이면, 두 문자가 서로 스왑 되어 동일해질 수 있음을 의미하므로 true를 반환합니다.
   • 그렇지 않으면 false를 반환합니다.

 

• 시간 복잡도: O(n)
  • 문자열의 길이 n에 비례하여 한 번 순회하면서 서로 다른 문자를 찾고, 필요한 계산을 수행합니다.
  • 따라서 시간 복잡도는 O(n)입니다.

• 공간 복잡도: O(1)
  • 추가적인 배열이나 리스트를 사용하지 않고, 상수 공간만 사용합니다.
  • 따라서 공간 복잡도는 O(1)입니다.

---

Runtime 결과