Word Ladder II - LeetCode

Problem

1. input:
2. output:

Idea

Solution

```kotlin
import java.util.*

class Solution {
    data class data(val begin: String, val path: MutableList<String>)
    val diffMap = hashMapOf<String, Boolean>()
    val connectMap = hashMapOf<String, MutableList<Int>>()
    fun findLadders(beginWord: String, endWord: String, wordList: List<String>): MutableList<MutableList<String>> {
        // 이어질 수 있는(차이 1) 문자 관계 미리 저장
        for (i in wordList.indices) {
            for (j in i +1 until wordList.size) {
                if (cntDiff(wordList[i], wordList[j])) {
                    connectMap.getOrPut(wordList[i]){mutableListOf()}.add(j)
                    connectMap.getOrPut(wordList[j]){mutableListOf()}.add(i)
                }
            }
        }
        if (!connectMap.containsKey(beginWord)) {
            for (idx in wordList.indices) {
                if (cntDiff(beginWord, wordList[idx])) connectMap.getOrPut(beginWord){mutableListOf()}.add(idx)
            }
        }
        var shortest = Int.MAX_VALUE // 최단 거리
        val answer = mutableListOf<MutableList<String>>()
        val queue = LinkedList<data>() // BFS seach용
        val visited = hashMapOf<String, Boolean>() // 최단 거리이기 때문에 visited 하나로 공유 가능
        queue.offerLast(data(beginWord, mutableListOf()))
        while (queue.size > 0) {
            val dt = queue.pollFirst()
            visited[dt.begin] = true
            if (dt.path.size > shortest) return answer // 더 이상 최단 거리와 같은 길이의 답이 나올 수 없음
            // 목적지 도달
            if (dt.begin == endWord) { 
                shortest = minOf(shortest, dt.path.size) // 최단거리 갱신
                dt.path.add(0, beginWord) // path 저장
                answer.add(dt.path)
                continue
            }
            // 다음 탐색
            for (idx in connectMap.getOrDefault(dt.begin, mutableListOf())) {
                if (visited.containsKey(wordList[idx])) continue 
                val tmpp = dt.path.toMutableList()
                tmpp.add(wordList[idx])
                queue.offerLast(data(wordList[idx], tmpp))
            }
        }
        return answer
    }

    // 두 문자의 차이가 1개인지 T/F 리턴
    fun cntDiff(s: String, e: String): Boolean {
        if (diffMap.containsKey("$s $e")) return diffMap["$s $e"]!! //memo
        var cnt = 0
        for (i in s.indices) {
            if (s[i] != e[i]) cnt++
        }
        diffMap["$s $e"] = cnt == 1
        diffMap["$e $s"] = cnt == 1
        return cnt == 1
    }
}
```

시간 복잡도: 

![Untitled](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/29a5cb18-5217-4cef-9d58-dfa1d1be5189/Untitled.png>)

Point