Leetcode139) Word Break
in Algorithms
BFS Solution
- add
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Queue<String> q = new LinkedList<>();
List<String> visited = new ArrayList<>();
q.add(s);
// q is not empty
while(!q.isEmpty()){
String cur= q.poll();
//base case
if(cur.equals("")){
return true;
}
if(visited.contains(cur)){
continue;
}
visited.add(cur);
for(int i =0;i<wordDict.size();i++){
String dictItem = wordDict.get(i);
if(cur.length()>=dictItem.length() && cur.substring(0,dictItem.length()).equals(dictItem)){
q.add(cur.substring(dictItem.length()));
}
}
}
return false;
}
}
# DP Solution
```java
public boolean wordBreak(String s, List<String> wordList) {
boolean[] dp = new boolean[s.length() + 1];
Set<String> set = new HashSet<>();
for (String word : wordList) {
set.add(word);
}
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && set.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
Brute Force
- list.contains(apple) => 이걸로 리스트 안에 apple이 있는지 없는지 간단하게 알 수 있다.
- stack 사용해서 previous true인 인덱스들을 집어 넣어줬다.
import java.util.*;
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int[] important = new int[s.length()];
important[0]=1;
Stack<Integer> prev= new Stack<>();
for (int i=0;i<s.length();i++){
important[0]=1;
if(important[i]==1){
for(int j=i+1;j<s.length()+1;j++){
if(wordDict.contains(s.substring(i,j))){
if(j==s.length()){
return true;
}else{
if(important[j]!=-1){
prev.push(i);
important[j]=1;
break;
}else{
continue;
}
}
}else if(j==s.length()){
important[i]=-1;
if(prev.empty()){return false;}
i=prev.pop()-1;
break;
}
}
}
}
return false;
}
}
잘못 생각한 부분
- lc 완전 처음 시작할 때라서 완전 기초적인 부분이넹.. 신기
- 단순한 건데 인지하지 못해서 틀렸다. 여기서 내가 루프를 다시 돌고 싶어서 for문 안에서, i=3으로 다시 넣어주면, 루프 끝나면서 1이 더해져서 4부터 시작한다. 3으로 돌아가서 루프 돌고 싶다면, i=2를 해줘야지 다음 루프에 i=3이 된다.
boolean a=true;
for(int i =0;i<10;i++){
if(a){
i=3;
a=false;
}
}
- a : index 0 에 다시 돌아왔을 때 false라고 생각했는데, 그게 아니다. 첫 단어부터 단추가 잘못끼였을 수 있으니까.. index 0 에 돌아왔고, important 어레이의 f들이 너무 많아져서 어떤 단어를 추가하려고 해도 못하고 그냥 for루프를 나갔을 때 false가 된다. 끝에 닿았는데 stack에 아무 숫자도 없어서 돌아갈 곳이 없으면 또 false가된다.
import java.util.*;
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
//일케 초기화 하면, 어레이 다 0으로 일단 초기화 됨. boolean 어레이일 경우, 다 false로 초기화.
int[] important = new int[s.length()];
important[0]=1;
Stack<Integer> prev= new Stack<>();
for (int i=0;i<s.length();i++){
// System.out.println(Arrays.toString(important));
important[0]=1;
/*aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
if(important[0]==-1){
return false;}
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa*/
if(important[i]==1){
for(int j=i+1;j<s.length()+1;j++){
if(wordDict.contains(s.substring(i,j))){
// System.out.println(s.substring(i,j));
if(j==s.length()){
return true;
}else{
if(important[j]!=-1){
prev.push(i);
important[j]=1;
break;
}else{
continue;
}
}
//만약 찾는 단어도 없는데 length도 맥시멈이라면?
}else if(j==s.length()){
//j가 마지막 인덱스에 닿았음에도, wordDict에 단어가 없다?(있으면 진즉에 브레이크로 나가야함) 너 false!
important[i]=-1;
//prev를 스택으로 안해서 문제인거같은데? ㅇㅇ 그래서 문제.
//그리고 더이상 팝할게 없으면 그럼 끝나는거...
if(prev.empty()){return false;}
i=prev.pop()-1;
break;
}
}
}
}
return false;
}
}
