CODEWITHSUNDEEP
javastringperformancedynamiccombinations
Raj
Raj

Reputation: 101

Time Complexity Difference between word break and Permutation

Word Break - Recurrence

The explanation in the above article makes sense. But why this cant be T(n) = nT(n-1) + 1? which results in n!. What am I doing wrong?

How is this different from permutation recursion, Permutation - recursion

Upvotes: 0

Views: 43

Answers (1)

ZhaoGang
ZhaoGang

Reputation: 4915

The difference is that in Permutation, let's say we have a sequence of a,b,c,d, for the first step, we can choose all of them, which make our first step have n possibilities. After that, for the seconed step, we still have n-1 possibilities for every first step. So we have n*(n-1)....

Whileas in Word Break, as sad in the link, lest's say we have a sequence of abcd and we have a word list a,b,c,d,ab,ac,ad,bc,bd,cd,.... We still have n choses for the first step: a,ab,abc,abcd. But after that, we don't have n-1 choses for every first step. For instance, if we chose abcd as the first step, we don't have a second step at all.

Upvotes: 1

Related Questions