leetcode hard : word ladder

https://leetcode.com/problems/word-ladder/description/

Word Ladder - LeetCode

 

풀기 전

* beginWord에서 한글자씩 바꿔가며 endWord로 가는 search문제다.

* beginWord가 탐색 트리의 루트노드가 되고 한 글자 바꾼 단어들중에 유효한 단어들이 자식노드가 된다.

* search + shortest + not weighted = BFS

* 단어 길이가 길지 않아서 다음 탐색 후보군은 그냥 노가다로 찾아도 될거같다.

* wordList를 set에 등록하면 조회, 삭제를 더 효율적으로 할 수 있다.

코드 설명

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordset = set(wordList)
        q = deque([(beginWord, 1)])
        while q:
            word, level = q.popleft()
            if word == endWord: return level
            for i in range(len(word)):
                for j in range(26):
                    nextWord = word[:i] + chr(ord('a')+j) + word[i+1:]
                    if nextWord in wordset:
                        wordset.remove(nextWord)
                        q.append((nextWord, level+1))
        return 0

* 큐에 (단어, 깊이)를 넣는다.

* 큐가 비어있지 않으면 계속 pop하면서 endWord랑 같은지 비교하고 아니면 다음 단어를 찾아 넣는다.

* 정답이 while 루프 안에서 안나왔으면 0을 리턴한다.

복잡도 분석

복잡도는.. 잘모르겠다. 일단 length of wordList에 비례하는건 확실한데..

알파벳(26글자) 특수성 + word길이가 10으로 고정돼있는거때문에 어렵네.

 

단어 길이를 M,

wordList 길이를 N이라고 하자.

일단 탐색트리엔 최대한으로 노드가 많아도 N개가 들어갈 수 있다. => N

노드(단어)를 하나 방문할 때마다

   endWord랑 pop한 word를 비교한다. => M

   단어의 각 글자를 26번씩 바꿔봐야한다. => M * 26

       바꿔보고 새 단어를 구성한다. => M

          새 단어가 wordset에 있는지 보고, 있으면 지우고 큐에 추가한다. => 1 (hash 구현이 아닌 tree구현인 set이면 log N일수도 있다.)

젤 깊은거 기준으로 N * M * 26 * M, 즉 O(M^2 * N)을 조심스럽게 예상해본다.