<Hard> Scramble String (LeetCode : C#)

https://leetcode.com/problems/scramble-string/

📕 문제 설명

같은 길이의 두 문자열이 주어졌을 때 s1을 scramble하여 s2를 만들 수 있으면 true 반환

• Scramble

1. 문자열 길이가 1이면 멈춤
2. 문자열 길이가 1보다 크면 다음을 수행
   2-1. 문자열을 2개의 하위문자열로 쪼갬
   2-2. 랜덤하게 두 하위 문자열을 swap하기 (이때 same order이어야함) [Ex) s = x + y, s = y + x]
   2-3. 2-1을 두 하위 문자열에 대해 재귀적으로 진행하기

• Input
  같은 길이의 두 문자열
• Output
  scramble 가능한지 여부 (bool)

예제

풀이

public class Solution {
    // 현재 s1과 s2가 서로 scramble 안되는 지에 대해 저장
    Dictionary<string, bool> mem = new Dictionary<string, bool>();
    public bool IsScramble(string s1, string s2) {
        int n = s1.Length;

        if(n != s2.Length) return false; // 길이 다르면 false
        if(s1.Equals(s2)) return true; // 같으면 true
        if(n == 1) return false; // 길이 1이면 scramble 안됨

        string key = s1 + " " + s2;
        if(mem.ContainsKey(key)) return false; // dict에 key 존재하면 false 케이스
        // 1 ~ string 길이까지 scramble 시도
        for(int i = 1; i < n; i++)
        {
            // swap 한거랑 안한걸로 각각 돌리기 
            if(IsScramble(s1.Substring(0, i), s2.Substring(0, i)) && IsScramble(s1.Substring(i), s2.Substring(i))) return true;
            else if(IsScramble(s1.Substring(n-i), s2.Substring(0,i)) && IsScramble(s1.Substring(0, n-i), s2.Substring(i))) return true;
        }
        // scramble 불가능한 케이스이므로 false로 dict에 저장
        mem.Add(key, false);
        return false;
    }
}

결과