[Leet Coding Challenge] Add and Search Word - Data structure design, 2020.08.01~07

 

leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3413/

Explore - LeetCode

 

문제 요약

이번에 풀어볼 문제는 Add and Search Word - Data structure design 라는 문제입니다.

문제에는 2가지 명령어가 있으며 여기에 따른 기능을 수행하면 됩니다. 

 

• addWord(String)->None :  문자열이 입력되며 a~z사이의 소문자가 입력됩니다.
• search(String)-> Bool : 문자열이 입력되며 해당하는 단어가 등록되어 있으면 True, 등록되어 있지 않으면 Fasle를 리턴합니다. 

검색 기능에서는 "."으로 표시되어 있는 곳에는 어떤 단어가 와도 일치한다고 판단하며 "."이 아닌 단어만 일치한다면 True를 리턴하면 됩니다.

 

문제풀이 IDEA

• 단어의 등록은 딕셔너리(해시테이블)을 이용하며 Key = 입력된 단어의 길이, Value = Array 형식이다. (Array에 추가하는 방식)
  -> 이렇게 진행하면 단어를 검색할때 검색할 단어의 길이 안에서만 탐색하면 된다.
• 단어의 검색은 같은 길이의 배열에 담겨진 단어들 중 조건에 맞는 것을 찾아 있으면 True, 없으면 False를 리턴한다.

 

전체적인 코드는 다음과 같습니다. 질문과 피드백은 언제나 감사드립니다.  

 

class WordDictionary:
    def __init__(self):
        self.wordDict = dict()        

    def addWord(self, word: str) -> None:
        width = len(word)
        if width in self.wordDict :
            self.wordDict[width].append(word)
        else :
            self.wordDict[width] = [word]

    def search(self, word: str) -> bool:
        comp = []
        for i, v in enumerate(word) :
            if v != "." :
                comp.append([i,v])
        if len(word) in self.wordDict :
            for i in self.wordDict[len(word)] :
                flag = True
                for j, v in comp :
                    if v == i[j] :
                        continue
                    else :
                        flag = False
                        break
                if flag :
                    return True
        return False