1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//import java.util.Stack

class Solution {
    var check: BooleanArray = booleanArrayOf()
    val list: MutableList<Int> = mutableListOf()
    // var stack: Stack<String> = Stack()

    fun solution(begin: String, target: String, word: Array<String>): Int {
        return if (word.contains(target)) {
            for (i in word.indices) {
                check = BooleanArray(word.size) { false }
                if (isConvertable(begin, word[i])) {
                    check[i] = true
    //                stack.push(begin); stack.push(word[i])
                    dfs(word[i], target, word, 1)
    //                stack.pop(); stack.pop()
                }
            }
            if (list.isEmpty()) 0
            else {
                list.forEach { println(it) }
                list.min()!!
            }
        }
        else 0
    }

    fun dfs(begin: String, target: String, word: Array<String>, count: Int) {
        if (begin == target) {
            list.add(count)
    //        println(stack.joinToString(" -> ", "", "(${count})"))
            return
        }

        for (i in word.indices) {
            if (check[i]) continue
            if (isConvertable(begin, word[i])) {
                check[i] = true
    //            stack.push(word[i])
                dfs(word[i], target, word, count + 1)
    //            stack.pop()
                check[i] = false
            }
        }
    }

    // fun isConvertable(begin: String, target: String): Boolean = begin.filter { target.contains(it) }.count() == begin.length - 1
    // begin의 각 Character를 target이 가지고 있는지 파악하여 변환 가능한 글자를 찾아내려 했지만
    // 이렇게 탐색을 할 경우 hht(begin)-> hih(target)가 가능하여 문제가 있음
    // i는 index라고 했을 때, begin[i] == target[i]로 탐색을 해야 올바른 방법

    fun isConvertable(begin: String, target: String): Boolean = BooleanArray(begin.length) { begin[it] == target[it] }.count { it } == begin.length - 1

}