[LeetCode] 139. Word Break (C++)

문제

 

https://leetcode.com/problems/word-break/

Word Break - LeetCode

 

풀이

 

난이도: Medium 

 

두 종류의 메모이제이션을 활용해서 해결하였다.

 

1. is_contain[i][j]

문자열 s의 i~j 부분 배열이 단어로 분해될 수 있는지 여부를 저장한다.

이를 확인하기 위해 모든 단어들을 언어에서 기본 제공하는 문자열의 find함수로 s에 포함 여부를 확인한다.

 

이때 s= "aaaaaaa" wordDict = ["aaaa", "aaa"]처럼 같은 문자로만 이루어진 입력이 있을 수 있다.

이런 경우는 아래와 같이 여러 위치에서 단어로 분해될 수 있으므로 find가 반환하는 word의 시작 위치의 바로 다음 위치부터 다시 단어를 find 해주어야 한다.

 

 

int len = s.length();
vector<vector<bool>> is_contain(len, vector<bool>(len, false));
 
string word;
int find_pos;
for (int i=0; i<wordDict.size() ; ++i) {
      word = wordDict[i];
      int start_pos = 0, word_len = word.length(), end_pos;
      while (start_pos < len) {
          find_pos = s.find(word, start_pos);
          if (find_pos == string::npos)
             break;  //문자열이 없는 경우
 
          end_pos = find_pos + word_len;
          is_contain[find_pos][end_pos -1] = true;
          start_pos = find_pos + 1;
      }
} 

 

 

 

2. is_connect[i]

i에서 s 문자열의 끝(end)까지가 단어들(wordDict)로 분해 가능한지 여부를 저장한다.

i는 뒤에서부터 진행해 주는데, 이는 i~end까지가 word로 분해 가능한지를 알 수 있다면 중복되는 연산을 줄일 수 있기 때문이다.

만약 is_connect[j+1]가 이미 false라면 j~end까지는 단어로 분해되지 않는 것을 의미한다.

그렇다면 i~j가 단어를 이루더라도(= is_contain[i][j]가 true) 연산을 할 의미가 없다.

 

vector<bool> is_connect(len+1, false);
is_connect[len] = true;
for (int i=len-1; i>=0 ; --i) 
     for (int j= i ;j<len ; ++j) 
          if (is_contain[i][j] && is_connect[j + 1]) {
              is_connect[i] = true;
              break;
          }

 

is_connect[0]이 true라면  0~end까지 모두 단어로 분해 가능함을 의미한다.

이러한 알고리즘의 복잡도는 find함수에 달려있는데 find함수의 성능은 사용하는 라이브러리마다 차이가 있다고 한다.

가장 빠른 문자열 search알고리즘은 O(n)의 복잡도를 가지므로 전체 복잡도는 O( wordDict.length * s.length^2) 정도로 예상한다.

 

 

 

추가적인 풀이를 소개하자면 string s에서 word를 찾았던 위의 풀이와 반대로

문자열을 자르고 해당 부분 문자열이 word안에 포함되어 있는지 찾는 방법도 있다.

이러한 풀이의 자세한 코드와 설명은 아래를 참조하자.

C++ Dynamic Programming simple and fast solution (4ms) with optimization

 

 

 

 

코드