LeetCode: 97번 (Interleaving String) [JAVA]

문제 링크

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

Interleaving String - LeetCode

풀이

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

1. 우선 받은 문자열 s1, s2, s3에 대해, s3의 길이가 s1과 s2 길이의 합이 아니라면 false 반환
2. 재귀 기반 탐색 함수 생성
   1) 인자로는 문자열 s1, s2, s3와 각각의 특정 위치를 나타내는 인덱스(s1Index, s2Index, s3Index)
   2) 기저조건으로는 문자열 s1, s2에 대해 어느 하나라도 문자열의 끝에 도달했다면, 다른 문자열의 남은 부분이 s3의 남은 부분과 동일한 지 아닌지에 따라 true와 false를 반환
   3) 이후엔 단순히 s3Index 위치의 s3 속 문자가 s1의 s1Index 위치의 문자와 동일하거나 s2의 s2Index 위치의 문자와 동일하다면 해당 재귀 함수를 다시 호출. 이 중 결과가 하나라도 true가 나온다면 전체 탐색 결과를 true로 설정
   4) 탐색 결과를 반환
   
3. 해당 전체 탐색의 시간을 줄이기 위해, 메모제이션을 적용
4. 재귀 호출 탐색의 결과를 답으로 반환

 문제 자체가 문자를 일일히 비교하는 탐색을 제외하고는 크게 방법이 없기에, 재귀 기반으로 탐색을 진행하는 함수를 작성하여 답을 찾아야 한다. 우선 문자열 s3가 s1과 s2의 합으로 구성되야 하기 때문에, s1, s2, s3에 대해, s3의 길이가 s1과 s2 길이의 합이 아니라면 false를 반환한다.
 그 다음에는 재귀 기반의 탐색 함수를 작성한다. 인자로는 문자열 s1, s2, s3와 해당 문자열 속 특정 위치를 나타내는 s1Index, s2Index, s3Index이다. 재귀 함수의 기저조건은 문자열 s1, s2에 대해 어느 하나라도 문자열의 끝에 도달했다면, 다른 문자열의 남은 부분이 s3의 남은 부분과 동일한 지 아닌지에 따라 true와 false를 반환하는 것이다. 그 이후에는 단순히 일일히 문자 비교를 하면 되기 때문에, s3 속 s3Index 위치에 해당하는 문자가 s1의 s1Index 위치와 동일하거나 s2의 s2Index 위치와 동일하다면 해당 재귀 함수를 호출하면 된다. 이 때 호출 결과가 한 번이라도 true가 나온다면, 전체 탐색 결과를 true로 하면 된다. 이후 전체 탐색 결과를 반환하면 된다.
 이 때 전체적으로 재귀 기반 탐색에 걸리는 시간을 줄이기 위해, 메모제이션을 적용해 시간을 단축할 수 있다. 인자로는 s2Index, s3Index를 활용하여, 해당 위치의 값이 이미 존재한다면 해당 값을 반환하고, 없다면 연산 결과를 저장해주면 된다.
 해당 함수의 구현이 완료했다면, 초기 s1, s2, s3에 대한 재귀 함수를 호출한 결과를 반환해주면 된다.

 

class Solution {
    Boolean[][] memory;

    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() != s1.length() + s2.length()) {//길이가 성립되지 않는다면
            return false;
        }

        //탐색 결과 저장 배열 초기화
        memory = new Boolean[s2.length() + 1][s3.length() + 1];

        return check(s1, s2, s3, 0, 0, 0);
    }

    boolean check(String s1, String s2, String s3, int s1Index, int s2Index, int s3Index) {
        if (s1.length() == s1Index) {//s1 끝에 도달한 경우 s2 나머지와 s3 나머지 비교
            if (s2.substring(s2Index).equals(s3.substring(s3Index))) {
                return true;
            } else {
                return false;
            }
        }

        if (s2.length() == s2Index) {//s2 끝에 도달한 경우 s1 나머지와 s3 나머지 비교
            if (s1.substring(s1Index).equals(s3.substring(s3Index))) {
                return true;
            } else {
                return false;
            }
        }

        if (memory[s2Index][s3Index] != null) {//기존 탐색 값이 존재하는 경우
            return memory[s2Index][s3Index];
        }

        boolean result = false;

        if (s3.charAt(s3Index) == s1.charAt(s1Index)) {//s1 부분과 맞는 경우
            result = check(s1, s2, s3, s1Index + 1, s2Index, s3Index + 1);
        }

        if (s3.charAt(s3Index) == s2.charAt(s2Index)) {//s2 부분과 맞는 경우
            result |= check(s1, s2, s3, s1Index, s2Index + 1, s3Index + 1);
        }

        return memory[s2Index][s3Index] = result;
    }
}

결과