[LeetCode] Python - 648. Replace Words

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

Replace Words - LeetCode

주어진 문장에서 각 단어들이 dictionary에 포함된다면 가장 짧은 어근이 되도록 교체하는 문제이다.

sentence의 공백을 기준으로 단어의 개수는 1이상 1000이하이고, dictionary의 길이도 1이상 1000이하이기 때문에 이중포문을 돌아도 시간초과가 나지 않습니다.

 

SSAFY 친구들과 같이 시간을 재고 문제를 풀면서 이중포문으로 풀면 시간초과가 날것같다고 당당하게 말했는데 제약사항을 잘못 읽었습니다..ㅎ

 

1. sentence를 공백기준으로 나눈다 -> words

2.  sentence -> dictionary 순으로 반복문을 돌면서 해당 단어가 dictionary로 시작한다면 words[i]를 해당 dictionary의 값으로 갱신시켜줍니다. startswith(d) 로 계속 검사를 해주기 때문에 동일 어근으로 시작하는 dictionary가 여러개 있더라도 가장 짧은 어근으로 대체가 됩니다.

3. join 함수를 사용하여, 공백을 넣고 문자열로 변환한 다음 리턴시켜줍니다.

 

Python Code

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        #sentence가 가장짧은 root를 가지게끔 찾기
        words = sentence.split(" ")
        for i in range(len(words)):
            for d in dictionary:
                if words[i].startswith(d):
                    words[i] = d
        return " ".join(words)