[Grind75-LeetCode] Word Break - Medium
접근
- dp
- dfs
- dfs + 메모이제이션
풀이
주어진 문자열 s를 단어 List에 들어있는 단어들로 구성이 가능한지 검사하는 문제이다. List에 들어있는 단어들은 중복이 없고 여러 번 사용이 가능하다. 문제 이해자체는 굉장히 쉽기 때문에 테스트케이스만 봐도 이해할 수 있다.
처음 접근으로 replace를 사용해 List에 들어있는 단어들을 공백으로 치환한 뒤 순회가 끝나고 문자열이 공백이 되었다면 만들 수 있는 것으로 true, 문자가 남아있다면 false를 반환하게 만들어봤다.
public boolean wordBreak(String s, List<String> wordDict) {
for (String word : wordDict) {
if(s.isEmpty())
return true;
s = s.replaceAll(word, "");
}
return s.isEmpty();
}그러나 이 방법을 사용하는 경우 순차접근을 통해 겹치는 단어를 제거해 버리기 때문에 s = "cars"인 경우 List = ["car", "ca", "rs"] 첫 번째 car이 제거되고 s = "s"만 남아 뒤에 있는 ca + rs로 cars를 만들 수 있지만 false가 반환되어 버린다. 이렇게 뒤에 상황을 고려해야 할 때 늘 나오던 방법이 있다. 바로 dp다.
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (String word : wordDict) {
if (i >= word.length() && s.startsWith(word, i - word.length())) {
dp[i] = dp[i] || dp[i - word.length()];
}
}
}
return dp[s.length()];
}dp를 통해 문자열 s를 쪼갠 후 부분 문자열이 wordDict에 의해 쪼개질 수 있는지 체크한다. 내용은 간단하다. i가 리스트에 들어있는 단어의 길이보다 큰 경우에만 수행한다. 여기서 i는 문자열 s의 인덱스를 나타내는 것이 아닌 실제 자리 수를 나타낸다. 문자열 s를 한 문자씩 쪼개서 검사하는데 s의 해당 인덱스 안에 word가 부분 문자열로 포함될 수 있는지 검사하는 것이다. 그렇기 때문에 s가 "abcde"이고 i가 2일 때 s는 ab가 되므로 word의 길이가 3과 같이 2보다 크다면 ab안에 포함될 수 없기에 검사할 필요가 없는 것이다. 그렇게 word가 s의 해당 자리안에 부분 문자열로 포함될 수 있다면 현재 s 부분 문자열 이 word로 끝나는지 검사한다.
s = "cars", dict = ["car", "ca", "rs"]
i = 1 s = "c"
1 >= 3(car) -> false
1 >= 2(ca) -> false
1 >= 2(rs) -> false
dp = [true, false, false, false, false]
i = 2 s = "ca"
2 >= 3(car) -> false
2 >= 2(ca) -> true
i - word.length() = 2 - 2 = 0
s.startsWith("ca", 0) -> true
dp[2] = dp[2] || dp[0] -> dp[2](false) || dp[0](true) = true
2 >= 2(rs) -> true
i - word.length() = 2 - 2 = 0
s.startsWith("rs", 0) -> false
dp = [true, false, true, false, false]
i = 3 s = "car"
3 >= 3(car) -> true
i - word.length() = 3 - 3 = 0
s.startsWith("car", 0) -> true
dp[3] = dp[3] || dp[0] -> dp[3](false) || dp(true) = true
3 >= 2(ca) -> true
i - word.length() = 3 - 2 = 1
s.startWith("ca", 1) -> ca.equals(ar) -> false
3 >= 2(rs) -> true
i - word.length() = 3 - 2 = 1
s.startWith("rs", 1) -> rs.equals(ar) -> false
dp = [true, false, true, true, false]
i = 4 s = "cars"
4 >= 3(car) -> true
i - word.length() = 4 - 3 = 1
s.startWith("car", 1) -> car.equals(ars) -> false
4 >= 2(ca) -> true
i - word.length() = 4 - 2 = 2
s.startWith("ca", 2) -> ca.equals(rs) -> false
4 >= 2(rs) -> true
i - word.length() = 4 - 2 = 2
s.startWith("rs", 2) -> rs.equals(rs) -> true
dp[4] = dp[4] || dp[2] -> dp[4](false) || dp[2](true) = true
dp = [true, false, true, true, true]
결과 s.length() = 4 dp[4] = true코드의 흐름을 작성한 것이다. 각 마지막 부분이 부분 문자열로 끝날 수 있을 때 앞부분 또한 부분 문자열로 만들 수 있었던 경우 해당 범위까지 부분 문자열 구성이 가능한 것으로 측정한다. 위의 rs로 s의 3,4번째를 구성할 수 있기에 dp 배열을 통해 2번까지 구성이 가능한지 체크하고 구성이 가능했다면 2번까지 구성한 단어와 현재 rs를 통해 s를 구성하게 되는 것이다.
살짝 애매한 성능의 코드이다. 제일 많이 분포된 8ms 보단 성능이 좋지만 제출에 따라 7ms까지 나오기 때문에 평균적인 성능이라 볼 수 있을 거 같다.
dp 최적화
dp로 풀어져 있던 코드들을 보니 살짝 다른 부분이 있었다.
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (String word : wordDict) {
int start = i - word.length();
if (start >=0 && dp[start] && s.startsWith(word, start)) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
다르다고 하기 보다 최적화 된 코드라고 할 수 있다. 미리 조건으로 dp[start] 값이 참인 경우만 수행하고 break를 해주는 것이다. 위에서 설명했듯이 rs를 cars와 비교할 때 앞의 2번째 자리 ca 부분이 맞는 문자가 없었다면 굳이 수행할 필요가 없는 것이다. rs를 cars의 3,4 번째와 매칭시킨다 해도 1,2 번째를 매칭시킨 단어가 없다면 rs도 사용할 수 없기 때문에 그런 경우를 걸러주는 것으로 연산을 많이 단축 시켰다.
dfs
당연하게도 모든 조합을 탐색하는 dfs를 사용해서도 풀어진다.
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] isVisited = new boolean[s.length()];
return dfs(s, 0, wordDict, isVisited);
}방문 배열을 만들고 dfs를 호출해 준다.
private boolean dfs(String s, int start, List<String> wordDict, boolean[] isVisited) {
if (start == s.length()) {
return true;
}
if (isVisited[start]) {
return false;
}
for (int i = 0; i < wordDict.size(); i++) {
String word = wordDict.get(i);
if (s.startsWith(word, start)) {
if (dfs(s, start + word.length(), wordDict, isVisited)) {
return true;
}
}
}
isVisited[start] = true;
return false;
}만약 시작 값이 문자열 길이와 같다면 만들 수 있는 것으로 true를 반환한다. 방문 했던 곳이라면 false를 반환해 다시 탐색하지 않게 한다. 그리고 단어 리스트를 탐색하여 문자열이 각 단어들로 시작이 가능하다면 그 이후를 재귀를 통해 진행한다.
0ms - dfs + 메모이제이션
0ms로 풀어졌던 코드인데 정말 복잡하게 구성이 되어 있었다. dfs와 메모이제이션을 통해 풀어진 코드였는데 구현된 메서드도 여러 개이고 왔다 갔다 하다 보니 헷갈리게 구성이 되어있다.
public boolean wordBreak(String s, List<String> wordDict) {
return recWay1(s, wordDict);
}구현해야 할 메서드다. 해당 메서드에선 recWay1 메서드로 작업을 넘긴다.
boolean recWay1(String s, List<String> wordDict) {
Boolean[] memo = new Boolean[s.length() + 1];
return wordBreak(s, wordDict, 0, memo);
}작업을 넘겨 받은 recWay1 메서드이다. 메모이제이션을 위한 배열을 만들고 오버로딩 된 wordBreak 메서드로 작업을 또 넘긴다. 메모이제이션 배열을 넘겨 실제 작업이 일어날 곳이다.
boolean wordBreak(String s, List<String> wordDict, int k, Boolean[] memo) {
if (k == s.length()) {
return true;
}
if (memo[k] != null) {
return memo[k];
}
for (int i=0; i<wordDict.size(); i++) {
String word = wordDict.get(i);
if (s.startsWith(word, k)) {
if(wordBreak(s, wordDict, k + word.length(), memo)) return memo[k] = true;
}
}
return memo[k] = false;
}오버로딩 된 wordBreak 메서드이다. k가 문자열의 길이와 같다면 만들 수 있다는 true를 반환한다. 메모이제이션 배열의 k가 null이 아니라면 해당 값을 반환한다. 메모이제이션을 위한 부분으로 해당 위치의 계산된 값이 있다면 해당 값을 반환하는 부분이다. 그리고 단어 리스트를 돌며 해당 단어로 문자열을 시작할 수 있다면 재귀 호출을 통해 나머지 부분을 해결하게 된다. 위의 dfs에 메모이제이션을 추가해 최적화된 버전이라고 할 수 있다.
boolean recWay2(String s, List<String> wordDict) {
Boolean[] memo = new Boolean[s.length() + 1];
return wordBreak2(s, new HashSet<>(wordDict), 0, memo);
}
boolean wordBreak2(String s, Set<String> wordDict, int k, Boolean[] memo) {
int n = s.length();
if (k == n) return true;
if (memo[k] != null) return memo[k];
for (int i=k + 1; i<=n; i++) {
String word = s.substring(k, i);
if (wordDict.contains(word) && wordBreak2(s, wordDict, i, memo)) {
return memo[k] = true;
}
}
return memo[k] = false;
}호출 되지는 않지만 다른 방법으로 풀어진 2번 코드가 존재해 코드가 복잡하고 길어보이는 것이었다. 리스트가 아닌 Set을 사용한 dfs로 1번 방법에 비해 성능이 떨어져 호출은 되지 않고 코드만 남아있는 것 같다. Set을 사용한 코드에선 매번 substring이 호출되어 성능에 영향을 주는 것인지 정확하게는 모르겠으나 6ms 정도의 성능으로 1번 코드인 0ms와는 차이가 좀 나는 방법이었다.
전체 코드
dp
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
final boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (String word : wordDict) {
if (i >= word.length() && s.startsWith(word, i - word.length())) {
dp[i] = dp[i] || dp[i - word.length()];
}
}
}
return dp[s.length()];
}
}
dp 최적화
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (String word : wordDict) {
int start = i - word.length();
if (start >=0 && dp[start] && s.startsWith(word, start)) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
dfs
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] isVisited = new boolean[s.length()];
return dfs(s, 0, wordDict, isVisited);
}
private boolean dfs(String s, int start, List<String> wordDict, boolean[] isVisited) {
if (start == s.length()) {
return true;
}
if (isVisited[start]) {
return false;
}
for (int i = 0; i < wordDict.size(); i++) {
String word = wordDict.get(i);
if (s.startsWith(word, start)) {
if (dfs(s, start + word.length(), wordDict, isVisited)) {
return true;
}
}
}
isVisited[start] = true;
return false;
}
}
dfs + 메모이제이션
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
return recWay1(s, wordDict);
}
boolean recWay2(String s, List<String> wordDict) {
Boolean[] memo = new Boolean[s.length() + 1];
return wordBreak2(s, new HashSet<>(wordDict), 0, memo);
}
boolean wordBreak2(String s, Set<String> wordDict, int k, Boolean[] memo) {
int n = s.length();
if (k == n) return true;
if (memo[k] != null) return memo[k];
for (int i=k + 1; i<=n; i++) {
String word = s.substring(k, i);
if (wordDict.contains(word) && wordBreak2(s, wordDict, i, memo)) {
return memo[k] = true;
}
}
return memo[k] = false;
}
boolean recWay1(String s, List<String> wordDict) {
Boolean[] memo = new Boolean[s.length() + 1];
return wordBreak(s, wordDict, 0, memo);
}
boolean wordBreak(String s, List<String> wordDict, int k, Boolean[] memo) {
if (k == s.length()) {
return true;
}
if (memo[k] != null) {
return memo[k];
}
for (int i=0; i<wordDict.size(); i++) {
String word = wordDict.get(i);
if (s.startsWith(word, k)) {
if(wordBreak(s, wordDict, k + word.length(), memo)) return memo[k] = true;
}
}
return memo[k] = false;
}
}'알고리즘 > 코딩테스트-Grind75' 카테고리의 다른 글
| [Grind75-LeetCode] String to Integer (atoi) JAVA (0) | 2024.11.12 |
|---|---|
| [Grind75-LeetCode] Partition Equal Subset Sum JAVA (0) | 2024.11.11 |
| [Grind75-LeetCode] Sort Colors JAVA (1) | 2024.11.09 |
| [Grind75-LeetCode] Accounts Merge JAVA (1) | 2024.11.08 |
| [Grind75-LeetCode] Time Based Key-Value Store JAVA (0) | 2024.11.07 |