backtracking dp solution, O(n) space. Who can tell me the time complexity?


  • 0
    R
    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
           boolean[] dp = new boolean[s.length()];
           wordBreak(s,dp, wordDict);
           return dp[0];
        }
        
        private void wordBreak(String s, boolean[] dp, Set<String> wordDict) {
            int end = s.length();
            int i = s.length()-1;
            while(i>=0) {
                end = s.length();
                if(wordDict.contains(s.substring(i,end))) {
                    dp[i] = true;
                }else {
                    while(--end>i) {
                        if(dp[end]&&wordDict.contains(s.substring(i,end))) {
                            dp[i] = true;
                            break;
                        }
                    }
                }
                i--;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.