23.09.2023
1048. Longest String Chain medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/348
Problem TLDR
Longest chain of words with single character added
Intuition
We can build a graph, then use DFS to find a maximum depth.
To detect predecessor, we can use two pointers.
Approach
Careful with two pointers: iterate over short string and adjust the second pointer for long, not vice versa.
Complexity
Time complexity:
O(w∗n^2), to build a graphSpace complexity:
O(n^2), for graph
Code
fun longestStrChain(words: Array<String>): Int {
fun isPred(a: String, b: String): Boolean {
if (a.length != b.length - 1) return false
var i = -1
return !a.any {
i++
while (i < b.length && it != b[i]) i++
i == b.length
}
}
val fromTo = mutableMapOf<String, MutableSet<String>>()
for (a in words)
for (b in words)
if (isPred(a, b))
fromTo.getOrPut(a) { mutableSetOf() } += b
val cache = mutableMapOf<String, Int>()
fun dfs(w: String): Int = cache.getOrPut(w) {
1 + (fromTo[w]?.map { dfs(it) }?.max() ?: 0)
}
return words.map { dfs(it) }?.max() ?: 0
}