-
[LeetCode] Word Break II알고리즘 2019. 12. 19. 17:07
문제
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [ "cats and dog", "cat sand dog" ]
Example 2:
Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] Output: []
Approach
어제 했던 Word Break과 유사한 문제인데
문자열을 나눌 수 있는 모든 단어 집합을 반환하는 것이 다르다.
기존 코드에서 Backtracking을 통해 단어 집합을 찾아내는 코드를 추가했는데
스트링이 엄청 길고 문자열이 한 글자씩 잘라지지만 결국 나눌 수는 없는 예시에서 TLE가 났다.
이를 해결하기 위해 문자열을 자르기 전 우선 주어진 단어로 문자열을 자를 수 있는지 부터 체크해서 해결하였다.
Code
https://github.com/chi3236/algorithm/blob/master/LeetCode_WordBreakII.cpp
'알고리즘' 카테고리의 다른 글
[LeetCode] Linked List Cycle (0) 2020.08.23 [LeetCode] Combination Sum (0) 2020.05.04 [LeetCode] Word Break (0) 2019.12.19 [LeetCode] Copy List with Random Pointer (0) 2019.12.18 [LeetCode] Gas Station (0) 2019.12.13