LeetCode알고리즘 Replace Words

오늘은 648번을 풀어보겠습니다.
중간 난이도고 61.0%의 성공률을 보입니다.

 

그럼 시작

영어에서는 root라는 개념이 있습니다.
이 루트 뒤에 successor가 따라와 더 긴 단어가 될 수 있습니다. 
예를 들어 root인 an와 그 뒤에 successor other이 붙으면 새로운 단어 another이 됩니다.

루트들로 구성된 딕셔너리가 주어지고
공백에 따라 분리되는 단어로 구성된 sentence를 root로 바꿔 재구성을 하면 됩니다.
만약 successor가 하나 이상의 root와 교체될 수 있다면 가장 짧은걸 root로 사용하면 됩니다.

즉 sentence안에 successors들이 있는 거고 root로 바꿀 수 있으면 바꾸어  문장을 재구성을 하면 됩니다.
여러 개의 root로 바꿀 수 있다면? 짧은걸 사용해라ㅇㅇ

 

주어진 예시를 보겠습니다.
(다섯 개 있는데 너무 많아서 세 개만..)

1번 예제를 보면 문장이 the cattle was rattled by the battery가 되고 이걸 공백에 따라 자르면 총 7개의 단어가 나옵니다.
- the
- cattle
- was
- rattled
- by
- the
- battery
이렇게 나와있고 root를 가진 딕셔너리는 ["cat", "bat", "rat"]으로 구성되어 있습니다.
the는 딕셔너리에 root가 없으니 그대로
cattle은 딕셔너리에 root cat이 있으니 cat으로 
was는 딕셔너리에 root가 없으니 그대로
rattled은 딕셔너리에 root rat이 있으니 rat으로
by는 딕셔너리에 root가 없으니 그대로
the도 딕셔너리에 root가 없으니 그대로
battery는 딕셔너리에 root bat이 있으니 bat으로 해서 문장을 재구성합니다.
그럼 the cat was rat by the bat이라는 문장이 만들어지게 됩니다.
이걸 리턴해주면 됩니다.

 

여러 개의 root로 바꿀 수 있다면? 짧은걸 사용해라ㅇㅇ이말은 3번째 예시로 확인할 수 있습니다.
문장이 a aa a aaaa 뭐 이런 식으로 와도 딕셔너리에 있는 가장 짧은 root는 a니 a를 사용하면 됩니다.

(네이밍이 구리네요..)

class Solution {
    func replaceWords(_ dictionary: [String], _ sentence: String) -> String {
        let split = sentence.split(separator: " ").map{ String($0) }
        var answer = ""
        
        for i in split {
            var has = false
            var list = [String]()
            
            for j in dictionary {
                if i.hasPrefix(j) {
                    list.append(j)
                    has = true
                }
            }
            
            if has {
                if list.count > 1 {
                    let shortest = list.sorted { a, b in
                        a.count < b.count
                    }.first!
                    answer.append(contentsOf: "\(shortest) ")
                } else {
                    answer.append(contentsOf: "\(list.first!) ")
                }
            } else {
                answer.append(contentsOf: "\(i) ")
            }
        }
        answer.removeLast()
        return answer
    }
}

먼저 주어진 문장을 잘라 단어로 만들어줍니다. 
각 단어를 돌면서 그 단어의 prefix가 딕셔너리에 있는 단어인지 확인해줍니다. (root 찾는 과정)
있으면 list에 root를 append 시켜줍니다. (list를 만든 이유는 여러 개의 root로 바꿀 수 있다면? 짧은걸 사용해라ㅇㅇ요거 때문이에요)
has는 true로 만들어줍니다. (root를 찾았을 때 has를 true로 만들어 줌)

for 루프를 나오고 has가 참인지 거짓인지 확인해줍니다.
참이면 root 리스트가 들어있을 list의 개수를 확인해줍니다.
1개면 그냥 list에 있는 root를 바로 answer에 붙이면 되고
1개 이상이면 가장 짧은 것을 찾기 위해 정렬해 answer에 root를 붙여줍니다.
거짓이면 그 단어 그대로 answer에 붙여줍니다.

단어를 붙일 때 공백도 같이 붙여줬기 때문에 마지막 공백은 removeLast()로 지워줍니다.
그리고 answer리턴하면 끝.

 

뭔가 간단한 건데 복잡하게 푼 느낌.

여튼 이렇게 했을 때 결과.

풀고 나서 확인해보니 이 문제의 주제는 TRIE...였네?
다시 풀어봐야겠네요^^,,,

 

resource: https://leetcode.com/problems/replace-words/