LeetCode - InterLeaving String

문제 설명

문제 설명이 좀 부실하다.

s1, s2가 주어지는데 s1,s2를 번갈아 가면서 concatination을 할 때, s3를 만들 수 있는지 없는지를 반환하라.

s1과 s2는 각각 앞에서부터 concatination을 시행해야만 한다.

해결 방법

최근 들어 LeetCode 하드 문제에 많이 대이고 있어서,, Hard 문제라고 하면 긴장부터 하고 푼다.

Dynamic Programming란으로 들어가서 문제를 풀었는데,
아무리 생각해도 Stack으로의 해결방법 밖에 떠오르지 않더라,,

Stack으로 해결한 방법은 다음과 같다.
위에 경우는 총 2가지의 경우로 나눌 수 있다.

1번째의 경우는 s1 != s2 일때 s1==s3 거나 s2 ==s3 일경우

위 경우는 별 신경 써주지 않아도 된다.
그냥 s1==s3이면 s1과 s3의 pointer를 하나씩 증가 시켜주면 된다.
s2 == s3인 경우는 s2와 s3의 Pointer를 하나씩 증가 시켜주면 되고

2번째의 경우는 s1==s2 일때 s1==s3거나 s2==s3일 경우

위 경우는 s1과 s2에서 어떤 char를 골라야 될지 모른다.
그래서 일단 s1으로 진행시켜놓고 만약 되지 않으면 s2로 다시 돌아와서 진행하는 방법이다. (생각해보면 backtracking도 가능할듯)

즉 s1으로 진행할때 스택에 s2의 상황과 s3의 위치를 저장시켜놓고 s1이 맞지 않으면 스택에서 빼놓으면
모든경우의 수를 전부 순회할 수 있다는 것

코드

import java.util.*;
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        
        Stack<NextPoint> stack = new Stack<>();
        
        int s1Index = 0;
        int s2Index = 0;
        int s3Index = 0;
        
        if(s1.length()+s2.length()!=s3.length()) return false;

        while(s3Index!=s3.length()||s2Index!=s2.length()||s1Index!=s1.length()){
            char c1 = s1Index<s1.length() ? s1.charAt(s1Index) : 'X';
            char c2 = s2Index<s2.length() ? s2.charAt(s2Index) : 'X';
            char c3 = s3.charAt(s3Index);
            
            if(c1==c2){
                if(c3==c1){
                    stack.push(new NextPoint(s1Index,s2Index+1,s3Index+1));
                    s1Index++;
                    s3Index++;
                }
                
            }else{
                if(c1==c3){
                    s1Index++;
                    s3Index++;
                }else if(c2==c3){
                    s2Index++;
                    s3Index++;
                }
                
            }
            
            if(c1!=c3&&c2!=c3){
                if(stack.isEmpty())
                    return false;
                NextPoint p = stack.pop();
                s1Index = p.s1;
                s2Index = p.s2;
                s3Index = p.s3;
            }
            
        }
        return true;
    }
}

class NextPoint{
    int s1;
    int s2;
    int s3;
    
    public NextPoint(int s1,int s2,int s3){
        this.s1 = s1;
        this.s2 = s2;
        this.s3 = s3;
    }
}

소감

처음에 생각한대로 알고리즘을 짰더니 바로 해결 됐다는 점에서 굉장히 좋았으나!
시간 복잡도에서 좋지 않은 모습을 보여줬다.

그래서 어떠한 방식으로 풀었나 봤는데,, 기가 막힌 방식으로 풀었더라..

이 Dynamic Programming은 문제를 많이 풀어보면서 생각을 많이 해야 겠음을 다시한번 느낀다..