LeetCode: 87번 (Scramble String) [JAVA]

문제 링크

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

Scramble String - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 문자열 a, b를 계속 분할하는 재귀함수를 생성
   1) 주어진 a와 b가 동일하다면 true 리턴
   2) a의 길이가 1 이하라면 false 리턴
   3) for문을 통해 i에 대해 1부터 a의 길이-1까지 다음을 반복
     a) a.substring(0, i)과 b.substring(a.length() - i)에 대해 재귀함수 호출 결과 AND a.substring(i)과 b.substring(0, a.length() - i)에 대한 재귀함수 호출 결과
     b) a.substring(0, i)과 b.substring(0, i)에 대해 재귀함수 호출 결과 AND a.substring(i)과 b.substring(i)에 대한 재귀함수 호출 결과
   4) 앞선 3번의 두 결과 중 하나라도 true가 나오면 결과를 true로 설정하고 break
   5) 결과 반환
2. 주어진 함수에 대해 재귀함수 호출

 해당 문제를 위해선 재귀 기반으로 완전 탐색을 진행해야 한다. 주어진 문자열 s1과 s2를 비교할 때, 특정 위치를 기준으로 s = x + y or s = y + x 형태의 뒤집힌 형태의 문자열을 모두 만들어 그 중 하나면 같다면 두 문자열이 조건에 부합하다고 할 수 있다. 해당 로직을 위해, 주어진 문자열 a와 b를 계속 분할하며 탐색하는 재귀함수를 생성해야 한다.
 우선 주어진 문자열 a와 b가 동일하다면 true를 리턴하고, a의 길이가 1 이하라면 false를 리턴한다. 그 다음에는 임시변수 i에 대해 for문을 통해 1부터 a의 길이-1까지 문자열을 특정 위치 기준으로 나누어 뒤집어보는 로직을 작성한다. a.substring(0, i)과 b.substring(a.length() - i)에 대해 재귀함수 호출 결과와 a.substring(i)과 b.substring(0, a.length() - i)에 대한 재귀함수 호출 결과를 AND로 묶은 결과 하나, a.substring(0, i)과 b.substring(0, i)에 대해 재귀함수 호출 결과와 a.substring(i)과 b.substring(i)에 대한 재귀함수 호출 결과를 AND로 묶은 결과 하나를 저장한다. 이들은 각각 비교할 두 문자열에 대해, s = x + y or s = y + x 중 하나만 맞으면 되기 때문에 이들 형태로 나누어 탐색을 진행하는 방식이다. 이후 두 탐색 결과 중 하나라도 true라면, 해당 문자열이 조건에 부합하기 때문에 결과를 true로 저장하고 반복문을 탈출한다. 이후 해당 함수의 반환값으로 결과를 반환하면 된다.
 앞선 함수의 구현을 완료했다면, 주어진 문자열 s1과 s2를 비교하는데는 단순히 해당 함수의 결과를 반환하면 된다. 다만 여기서 문제 해결에 끝이 아니라, 재귀 기반의 탐색 과정에서 탐색 횟수를 줄이기 위해 메모제이션을 적용할 수 있다. 문자열들을 계속 분할하며 탐색을 하다보면 동일한 문자열을 탐색하는 경우의 수가 생기기 때문에, 해당 탐색의 결과를 미리 저장해놓으면 재활용이 가능하다. 이를 위해 String, Boolean을 담는 HashMap을 생성하고, 키 값으로는 주어진 두 문자열을 적당한 구분자로 이어 붙인 키를 활용한다. 이후 특정 재귀 탐색의 결과를 해당 키를 바탕으로 저장하며, 다른 함수에서 탐색을 진행할 때 해당 키값으로 결과가 있다면 해당 결과를 바로 반환하면 된다.

 

class Solution {
    Map<String, Boolean> map = new HashMap<>();

    public boolean isScramble(String s1, String s2) {
        return check(s1, s2);
    }

    public boolean check(String a, String b) {
        if(a.equals(b)){
            return true;
        }

        if(a.length() <= 1) {
            return false;
        }

        boolean result = false;
        String key = a + "/" + b;//메모제이션을 위한 키값 설정

        if(map.containsKey(key)) {//결과가 존재한다면
            return map.get(key);
        }

        for (int i = 1; i < a.length(); i++) {//a 길이만큼의 경우의 수 모두 탐색
            boolean swap = check(a.substring(0, i), b.substring(a.length() - i)) && check(a.substring(i), b.substring(0, a.length() - i));
            boolean unswap = check(a.substring(0, i), b.substring(0, i)) && check(a.substring(i), b.substring(i));

            if (swap || unswap) {//둘 중 하나라도 true라면
                result = true;
                break;
            }
        }

        map.put(key, result);//탐색 결과 저장

        return result;
    }
}

결과