[LeetCode- Part. 1] 5. 단어 나누기 # (+DP)

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

Word Break - LeetCode

---

문자 s와 문자열 리스트 wordDict이 주어지면, wordDict에 있는 단어로 모두 분리되면 true 리턴

여러번 재사용 가능

 

DP 이용 1차시도

-> 실패

import java.util.*;
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n=wordDict.size();
        int N=s.length();
        String[][] dy=new String[N+1][2];
       for(int i=0; i<N+1; i++){
         Arrays.fill(dy[i], "N");
        }
   
        int j=0;
        for(int i=0;i<N+1;i++){
            
            String tmp="";
            String tmp2="";
            tmp=s.substring(j, i);
            tmp2=s.substring(i);
            if(wordDict.contains(tmp)&& wordDict.contains(tmp2)) return true;
            
            System.out.println("자름 "+tmp);
            if(wordDict.contains(tmp)){
                dy[i][0]=tmp;
                for(int k=j; k<=i; k++) {
                    System.out.println(i+" "+dy[k][0]);
                    dy[k][1]="Y";
                }
                j=i;
                
            }
        }
        for(int i=0;i<N+1;i++){
            System.out.println("result"+dy[i][1]);
            if(dy[i][1].equals("N")) return false;
        }
        
        return true;
    }
}

 

DP 이용 2차시도

-> 같은 단어 반복일 때 처리 실패

class Solution {
    static boolean answer=false;
    static int n;
    public boolean wordBreak(String s, List<String> wordDict) {
        //Input
        // "goalspecial"
        // ["go","goal","goals","special"]
        if(wordDict==null || wordDict.size()==0) return false;
        if(wordDict.size()==1 && !wordDict.get(0).equals(s)) return false;
        n=wordDict.size();
        String [][] dy = new String[n][2];
        for(int i=0;i<n;i++) dy[i][0]=wordDict.get(i);
        String tmp="";
        int j=0;
        for(int i=0;i<s.length();i++){
            tmp=s.substring(j,i);
            if(wordDict.contains(tmp)){
                j=i;
                dy[wordDict.indexOf(tmp)][1]="Y";
            }
        }
        answer=false;
        for(int i=0;i<n;i++){
            DFS(i, dy, s, "");
            if(answer)break;
        }
        
        return answer;
    }
    private void DFS(int L, String[][] dy, String s, String str){
        System.out.println("L "+L+" str: "+str+" s: "+s);
        if(str.equals(s)) {
            answer= true;
        }
        if(!answer){        
        if(s.length()<str.length() || L>n) return;
        if(s.length()>str.length()&&L==n) L=0;

        //System.out.println(L+" "+str+" "+dy[L][0]);
        DFS(L+1, dy, s, str+dy[L][0]);
        //DFS(L+1, dy, s, str);
        }
    }
}

 

같은 문자가 반복되는 경우 에러 발생

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Collections.sort(wordDict, (o1, o2) -> o2.length()-o1.length());
        for(String str : wordDict) System.out.println(str);
        
        int n=s.length();
        char[] dp = new char[n];
        Arrays.fill(dp, 'N');
        String tmp="";
        int j=0;
        for(int i=0;i<n;i++){
            String tmp2="";
            tmp = s.substring(j,i+1);
            tmp2=s.substring(i+1);
            if(wordDict.contains(tmp)){
                for(int k=j;k<=i;k++) dp[k]='Y';
                j=i+1;
            }   
            
        }
        
        for(int i=0;i<n;i++)System.out.println(dp[i]);
        for(int i=0;i<n;i++){
            if(dp[i]=='N') return false;
        }
        return true;
    }
}

---

문제 해결 방법

1. s에서 in 문자를 만들어서 wordDict에 있는지 체크한다.

2. for을 2번 돌려서 s.substring(0,2) 이런식으로 뺀다.

3. boolean 타입 dp배열을 만들고 이정표를 체크한다.

 

boolean[글자수 +1 ] dp;
for(int i=첫 번째 글자; i<=마지막 글자; i++){
 for(int j=DP 배열 처음부터; j<해당 문자 전까지; j++){
 	if(DP배열의 해당 문자가 참일 경우 && 자른 문자열도 존재할 경우)
     DP[해당 문자의 위치] = 참;
  }
  return DP[마지막 문자];
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //1.ds
        //단어들이 중복을 허용하지 않아야한다.
        Set<String> set=new HashSet<>(wordDict);
        
        //DP는 0이라는 시작하는 점이 필요하므로, N+1개
        //DP배열 : 현재 위치까지 전부 사전에서 찾을 수 있다는 뜻
        boolean[] dp = new boolean[s.length()+1];
        dp[0]=true;
        
        //2. loop
        //이중 for문을 이용해 반복한다.
        //글자의 길이는 1부터 시작하고, substring은 뒷자리는 포함하지 않으므로,
        for(int i=1;i<=s.length();i++){
            for(int j=0;j<i;j++){
                System.out.println("j: "+j+" i:"+i+" "+(s.substring(j, i))+" dp["+j+"]: "+dp[j]);
                //앞단이 모두 true여야 i번째도 true일 수 있다.
                
                //따라서 j번째가 모두 참이고, 현재위치까지 자른 값이 set에 존재할 경우 i번째도 true
                if(dp[j] && set.contains(s.substring(j,i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        //dp의 경우 마지막방이 true여야 참
        return dp[s.length()];
    }
}

 

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n=s.length();
        boolean[] dp = new boolean[n+1];
        dp[0]=true;
        
        Set<String> set = new HashSet<>(wordDict);
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&set.contains(s.substring(j,i))){
                    dp[i]=true;   
                    break;
                }
            }
        }
        return dp[n];
    }
}