给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
dictbreak
函数中的循环里的递归调用,设字符串长度为n,计算次数(只考虑循环)为T(n),则T(n)=1+T(n-1)+1+T(n-2)+...+1+T(1)+1+T(0);
其中,T(0)=0,T(1)=1, 则T(n)=sigma(T(n-1))+n;
所以,sigma(T(n)) = sigma(T(n-1))+T(n)=n+2sigma(T(n-1));
因此有,sigma(T(n)) +n =2sigma(T(n-1))+2(n-1)+2;
递归一下,有sigma(T(n))+n = 2^(n-1) x sigma(T(1)+1)+sigma(2^(n-1)=O(2^n); 由于T(n)和sigma(T(n-1))+n复杂度相同,所以时间复杂度为指数级别。。。
当然不会通过。