리트코드 - 139. Word Break

리트코드 - 139. Word Break

출처 - https://leetcode.com/problems/word-break/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 문자열 s와 문자열 사전 wordDict가 있을 때, 만약 s를 하나 이상의 사전 단어로 이루어진 공백으로 구분된 시퀀스로 나눌 수 있다면 true를 반환합니다.

단어 사전에서 동일한 단어가 세그먼트 내에서 여러 번 재사용될 수 있음에 유의하세요.

 

의사코드

wordDict의 크기가 0이면 false 리턴 wordSet = wordDict를 Set으로 변경 n = s.length dp = new boolean[n + 1] dp[0] = true 반복문 시작 (i = 1, i <= n, i++)     반복문 시작 (j = i -1, j >=0, j--)         if (dp[j] && wordSet이 s.substring(j, i)를 가짐)             dp[i] = true             break     반복문 종료 반복문 종료 dp[n] 리턴

 

풀이코드

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
    	if (wordDict.size() == 0) {
        	return false;
        }
        Set<String> wordSet = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
}

 

코드설명

String s에서 wordDict에 존재하는 단어로만 구성되어 있는지 확인하는 문제이다.

주의할 것이 주어진 예제 2번을 보면 string이 "catsandog"로 주어지고 wordDict가 cat, cats, and, dog가 모두 주어짐에도 false를 리턴하고 있다.

즉, wordDict에 해당하는 단어를 찾으면 그 단어를 제외하고 다시 wordDict의 단어들로 분류 가능한가? 가 정확한 요구사항이다.

 

이제 단어를 쪼개서 확인하는 기능을 만들어야 한다.

 

dp 배열을 boolean으로 만들고 특정 인덱스까지 단어를 만들수 있으면 true로 바꾸어주면 된다.

글로는 어려우므로 위의 catsandog를 예로 들겠다.

먼저 dp배열을 한 칸 더 크게 만들어서 dp[0]을 true로 하여 시작한다.

 

단어 cat을 포함하고 있으므로, dp[3]에 true를 저장한다.

그리고 단어 cats도 포함하고 있으므로, dp[4]도 true를 저장한다.

다음으로 and라는 단어를 포함하는지 확인하는데, and 앞이 true로 끝나야만 한다.

true로 끝나므로 dp[7]에도 true를 저장할 수 있다.

 

마지막으로 dog를 보는데, dog 앞이 false 이므로 true로 바꿀 수 없다.

따라서 이 단어는 분류할 수 없다.

 

catsanddog 였다면 어떨까?

 

true를 리턴할 수 있게 된다.

마지막 dp값이 true면 자를수 있고, false면 자를수 없는 값이다.

 

이를 다시 정리하면 두 줄로 정리 가능하다.

 

1. String s가  단어를 포함하고 있는가?

2. 그 단어 앞의 dp배열이 true인가?

 

이를 구현하면 아래와 같다.

 

구현코드

for (int i = 1; i <= n; i++) {
    for (int j = 0; j < i; j++) {
        if (dp[j] && wordSet.contains(s.substring(j, i))) {
            dp[i] = true;
            break;
        }
    }
}

먼저 성능을 개선하지 않았던 원래 코드다.

wordDict가 list라서 선형 검색을 하다보니 set인 wordset으로 바꾸어서 성능을 향상 시켰다. set은 hash 값으로 조회하기 때문이다.

 

i는 단어를 처음부터 끝까지 순회하는 인덱스이고, j는 문자열의 앞을 확인하기 위한 인덱스이다.

 

i가 올라갈때마다 j가 0부터 조회를 하다보니 상당히 비효율적인 코드가 되었다.

 

리팩토링

for (int i = 1; i <= n; i++) {
    for (int j = i - 1; j >= 0; j--) {
        if (dp[j] && wordSet.contains(s.substring(j, i))) {
            dp[i] = true;
            break;
        }
    }
}

 

이전 코드는 앞에서부터 dp[j] && wordSet.contains(s.substring(j, i)) 조건을 확인하고 있었다.

j를 뒤에서부터 확인하면 앞의 true가 있는 조건에서 빠르게 반복문을 break 할 수 있다.

 

리팩토링 전 런타임은 9ms이고, 리팩토링 후 런타임은 3ms 이다.

 

시간복잡도 - O(n^2)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

성능 튜닝

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (wordDict.size() == 0) return false;
        Set<String> wordSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        
        int maxLength = getMaxWordLength(wordDict);

        for (int i = 1; i <= s.length(); i++) {
            for (int j = Math.max(0, i - maxLength); j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[s.length()];
    }
    private int getMaxWordLength(List<String> wordDict) {
        int maxLength = 0;
        for (String word : wordDict) {
            maxLength = Math.max(maxLength, word.length());
        }
        return maxLength;
    }
}

리팩토링 하기 전 코드를 가지고 고민하다가 단어 한개의 최대 길이 부터 조회하면 될 것 같다는 생각이 들었다.

getMaxWordLength 메소드를 만들어 wordDict 배열에 있는 단어의 최대길이를 저장하고,

for문을 돌때 j가 i - maxLength부터 돌게하면 중복을 피할 수 있다.

 

최종적으로 런타임이 3ms -> 1ms가 되었다.

 

정리

문자열을 사전에 주어진 단어들로 나눌 수 있는지 판단하기