example to explain how to calculate Time Complexity
the memo size means each state will be calculated only once
how about the TC in each state?
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
return dfs(s,wordDict,0,new Boolean[s.length()]);
}
// Given n as the length of s, m as the length of wordDict, and k as the average length of the words in wordDict,
public boolean dfs(String s, List<String> wordDict,int start,Boolean[] memo) {
if(start == s.length()){
return true;
}
if(memo[start] != null) return memo[start]; // n states
boolean res = false;
for(String str: wordDict){ // to calculate each state, iterate m times
if(start+str.length() > s.length()) continue;
String t = s.substring(start,start+str.length()); // cost k times
if(t.equals(str) && dfs(s,wordDict,start+str.length(),memo)){
res = true;
}
}
return memo[start] = res;
}
}
so the TC is O(n * m * k)
标签：top,TC,down,start,length,str,wordDict,memorization,memo From： https://www.cnblogs.com/sabertobih/p/17643343.html