Recently, I had to implement the following algorithm (similarly). Code in Kotlin:
fun solution(keyword: String, lyric: String): Boolean {
val lyricWords = music.split(" ")
var index = 0
for (word in lyricWords) {
for (c in word) {
if (c == keyword[index]) {
index++
break
}
if (index == word.size) return true
}
return false
}
My intuition to the runtime analysis, given n to be the length of lyric and m the length of keyword:
- O(n) for the
splitoperation, since it should scan the entire string looking for spaces. - Roughly O(n) for the second for-loop, since it would iterate through all the characters for every word in the worst case.
- O(m) for the internal for-loop over all characters in keyword.
- Overall, should that take under O(n+m)?
What would be the time complexity for the above function?
split(), constant-time access to each element the collectionlyricWords, and constant-time access the $i$-th character in a string, the time complexity would be $O(n)$. Notice that if $m = \omega(n)$ you still do only $O(n)$ iterations of the inner loop. This is tight, in the sense that there are some inputs for which the time spent is $\Omega(n)$. $\endgroup$in). Not everyone here knows Kotlin, and the details of Kotlin are off-topic here. We'd prefer that you share your code as concise pseudocode. 2. What attempts have you made? See cs.stackexchange.com/q/23593/755 for the general approach. $\endgroup$