[Java] LeetCode 472. Concatenated Words

[Java] LeetCode 472. Concatenated Words

 

문   제 : 

문자열 배열 words가 주어진다.

words에 있는 각 문자열들중 자신을 제외한 words 안에 있는 문자열들로만 이루어져 있는 문자열만 반환해라.

 

{ 1 <= words.length <= 10^4 }

{ 1 <= words[i].length <= 30 }

{ All the Strings of words are unique. }

{ words[i] are only lowercase }

 

Example )

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: 
"catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

///////////////////////////////////////////////////////

Input: words = ["cat","dog","catdog"]
Output: ["catdog"]

 

---

접   근 : 

HashSet 을 이용해 겹치지 않는 문자들을 세트로 저장하고 각 단어들을 쪼개어 가면서 쪼갠 부분이 Set에 있는지 확인한다.

재귀함수로 구현한다.

 

 

---

해   결 : 

각 단어들을 함수에 집어넣고 ConcatenatedWord인지 아닌지 판별한다.

함수 : 

단어를 두 부분으로 나누어 본다.

앞 부분, 뒷 부분으로 나누어 볼 때, 앞 부분이 Set에 있는 단어이고, 뒷 부분또한 Set에 있거나 또 쪼개었을 때 있는 단어라면 이 단어는 Concatenated 하다고 할 수 있다.

이 과정을 단어의 길이만큼 반복한다.

 

---

함수 작성

 

 

public boolean isConcatenatedWord(Set<String> set, String word){
    for(int i=1; i<word.length(); i++){
        String first = word.substring(0, i);
        String second = word.substring(i, word.length());

        if(set.contains(first) && (set.contains(second) || isConcatenatedWord(set, second) == true)){
            return true;
        }  
    }
    return false;
}

 

 

---

 

Hash Set 생성, 단어 추가

결과 단어 저장할 List 선언

 

Set<String> set = new HashSet<>();
ArrayList<String> concatenatedWords = new ArrayList<>(); // 결과 저장
for(String word: words){
    set.add(word);
}

 

---

 

각 단어를 함수를 통해 검사 후 맞다면 결과 List에 추가

 

for(String word: words){
    if(isConcatenatedWord(set, word) == true){
        concatenatedWords.add(word);
    }
}

 

 

---

결   과  :

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> set = new HashSet<>();
        ArrayList<String> concatenatedWords = new ArrayList<>();
        
        for(String word: words){
            set.add(word);
        }

        for(String word: words){
            if(isConcatenatedWord(set, word) == true){
                concatenatedWords.add(word);
            }
        }
        return concatenatedWords;

    }
    public boolean isConcatenatedWord(Set<String> set, String word){
        for(int i=1; i<word.length(); i++){
            String first = word.substring(0, i);
            String second = word.substring(i, word.length());

            if(set.contains(first) && (set.contains(second) || isConcatenatedWord(set, second) == true)){
                return true;
            }  
        }
        return false;
    }
}