C# DP Solution


  • 0
    K

    To solve this problem, you can first solve the substrings of the given string. For each given substring, we check whether we can construct a sub answer by combining a previous answer for a substring and the wordDict. Final answer is given in the final array entry. The reason we set the array to length + 1 is so that we can start off the DP. You can also check dp[j] OR first index, and account for indices but that is messier.

    public class Solution {
        public bool WordBreak(string s, ISet<string> wordDict) {
            bool[] dp = new bool[s.Length + 1];
            dp[0] = true;
            for(int i = 1; i < s.Length + 1; ++i){
                for(int j = 0; j < i; ++j){
                    if(dp[j] && wordDict.Contains(s.Substring(j,i-j))){
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.Length];
        }
    }
    

Log in to reply
 

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