[LeetCode- Part. 2] 3. 두 단어 이상 연결된 단어 #

https://leetcode.com/problems/concatenated-words/submissions/

Concatenated Words - LeetCode

 

 

참고 자료

https://and-some.tistory.com/928

[LeetCode- Part. 1] 5. 단어 나누기 #

 

[LeetCode- Part. 1] 5. 단어 나누기 #

 

 

타임 리밋 발생

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        //Set<String> set = new HashSet<>();
        List<String> result = new ArrayList<>();
        List<String> wordlist = new ArrayList<>(Arrays.asList(words));
        int N=words.length;
        for(int k=0;k<N;k++){
            String s=words[k];
            int n=s.length();
            boolean[] dp = new boolean[n+1];
            dp[0]=true;

            Set<String> tmpset = new HashSet<>(wordlist);
            tmpset.remove(s);
            
            for(int i=1;i<=n;i++){
                for(int j=0;j<i;j++){
                    if(dp[j]&&tmpset.contains(s.substring(j,i))){
                        dp[i]=true;   
                        break;
                    }
                }
            }
            if(dp[n]) result.add(s);
        }
        
        return result;
    }
}

 

 

---

문제 해결 순서

1. 단어 목록을 set에 넣는다.

2. 가장 긴 단어를 찾아, substring을 하면서 단어가 존재하는지 찾아 dp 배열에 저장한다.

3. 배열 끝을 확인해 true이면 리스트에 넣는다.

 

 

구현 순서

1. set에 단어 목록을 넣는다.

2. 리스트를 이용해 단어의 길이 내림차순으로 정렬한다.

3. 리스트에서 제일 긴단어 순으로 꺼내, DP 배열을 만들어 두 개 이상의 단어로 이루어졌는지 확인해 결과 리스트에 추가한다.

4. 꺼낸 이후에는 리스트와 set에서 제거하는 과정을 거친다.

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        //배열을 리스트로 만드는 방법 - Arrays.asList()
        List<String> raw = new ArrayList<>(Arrays.asList(words));
        Collections.sort(raw, (o1, o2)-> o2.length()-o1.length());
                
        Set<String> set = new HashSet<>(raw);
        List<String> list = new ArrayList<>();
        while(set.size()>2){
            String s = raw.get(0);
            raw.remove(0);        
            set.remove(s);
            boolean[] dp = new boolean[s.length()+1];
            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;
                    }
                }
            }
            if(dp[dp.length-1]) list.add(s);
       }
        
        return list;
    }
}

---

+) 세련된 풀이

 

1. 단어의 길이를 오름차순 정렬해, 짧은 단어부터 Set에 넣는다.

2. DP를 수행하면서, set에 존재하면 result에 추가하는 방식

3. DP의 특징과 같이 배열의 마지막이 true이면 result에 추가한다.

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        //1. ds
        //결과 리스트
        List<String> result = new ArrayList<>();
        //단어를 유일하게 담는 set
        Set<String> set = new HashSet<>();
        //단어 길이 오름차순 정렬
        Arrays.sort(words, (o1, o2)-> o1.length()-o2.length());
        //2. loop
        //: 길이 내림차순으로 정렬된 배열에서 하나씩 꺼내, 파라미터로 전달해 함수 호출한다
        for(int i=0;i<words.length; i++){
            if(makeWord(words[i],set)){
                result.add(words[i]);
            }
            set.add(words[i]);
        }
        return result;
    }
    private boolean makeWord(String word, Set<String> set){
        //1.ds
        if(set.isEmpty()) return false;
        boolean [] dp = new boolean[word.length()+1];
        dp[0]=true;
        
        
        //2.loop
        //단어 첫번째 문자부터 마지막 문자까지 돌면서 DP 수행
        for(int i=1;i<=word.length();i++){
            for(int j=0;j<i;j++){
                if(dp[j]&& set.contains(word.substring(j,i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[word.length()];
    }
}

 

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        
        Arrays.sort(words, (o1,o2)->o1.length()-o2.length());
        Set<String> set = new HashSet<>();
        List<String> result = new ArrayList<>();
        int n=words.length;
        for(int i=0;i<n;i++){
            System.out.println(words[i]);
            if(makeWord(words[i], set)) result.add(words[i]);
            
            set.add(words[i]);
        }
        return result;
    }
    private boolean makeWord(String s, Set<String> set){
        
        int n=s.length();
        boolean[] dp = new boolean[n+1];
        dp[0]=true;
        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];
    }
}