thảo luận Leetcode mỗi ngày

function wordBreak(s: string, wordDict: string[]): boolean {
    const n = s.length, set = new Set(wordDict) ;
    let dp = Array(n+1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && set.has(s.substring(j,i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
};

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        var dp = new bool[s.Length];
        for(int i = 0; i< dp.Length; i++)
        {
            foreach(var item in wordDict)
            {
                if(i  < item.Length - 1)
                    continue;

                if(i == item.Length - 1 || dp[i - item.Length])
                {
                    if (s.Substring(i - item.Length + 1, item.Length).Equals(item)) {
                        dp[i] = true;   
                        break;
                    }
                }
            }
        }

        return dp[s.Length - 1];
    }
}

public class Solution {
    string s;
    Dictionary<char, List<string>> dict;
    bool?[] memo;

    public bool WordBreak(string s, IList<string> wordDict) {
        this.s = s;
        memo = new bool?[s.Length];
        dict = new ();
        for (var c = 'a'; c <= 'z'; c++)
            dict[c] = new List<string>();
        foreach (var word in wordDict.OrderByDescending(word => word.Length))
            dict[word[0]].Add(word);

        return solve(0);
    }

    public bool solve(int i)
    {
        if (i >= s.Length)
            return true;
        if (memo[i] != null)
            return memo[i].Value;

        foreach (var word in dict[s[i]])
        {
            int j = word.Length - 1;
            for (; j >= 0 && i+j < s.Length; j--)
            {
                if (word[j] != s[i+j])
                    break;
            }
            //Console.WriteLine($"{word}, {j}, {i}");
            if (j < 0 && solve(i+word.Length))
            {
                memo[i] = true;
                return true;
            }
        }
        memo[i] = false;
        return false;
    }
}

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        
        @cache
        def dfs(curIdx: int) -> bool:
            if curIdx == len(s):
                return True
            
            
            for word in wordDict:
                if s.startswith(word, curIdx):
                    if dfs(curIdx + len(word)):
                        return True
            
            return False
        
        return dfs(0)

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        int dp[n];
        memset(dp, false, sizeof(dp));
        for(int i = 0; i < n; ++i){
            for(string& word : wordDict){
                int l = word.size();
                // out of word or s[0...i - l] cant be constructed
                if(i - l + 1 < 0 || (i >= l && !dp[i - l])) continue;
                if(s.substr(i - l + 1, l) == word) dp[i] = true;
            }
        }
        return dp[n - 1];
    }
};

struct Solution {
    bool wordBreak(string_view s, const vector<string>& wordDict) {
        vector<bool> able(s.size() + 1, false);
        able[0] = true;
        for (size_t i = 0; i < s.size(); ++i) {
            if (!able[i]) continue;
            for (const auto& word : wordDict)
                if (s.substr(i).starts_with(word)) able[i + word.size()] = true;
        }
        return able[s.size()];
    }
};