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

class Trie: 
    def __init__(self):
        self.children = {} 
        self.word = False
    
    def addWord(self, word):
        curNode = self
        for char in word:
            if char not in curNode.children:
                curNode.children[char] = Trie()
            curNode = curNode.children[char]
        curNode.word = True 

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        dp = {} # map startIndex -> list of sentences in s[startIndex.. ]
        dp[n] = [[]] 
        trie = Trie()
        for word in wordDict:
            trie.addWord(word)
        for start in range(n - 1, -1, -1):
            curTrieNode = trie
            curSentenceList = []
            for end in range(start, n):
                curTrieNode = curTrieNode.children.get(s[end], None)
                if not curTrieNode: # s[start.. end] is not a prefix of any word => early break
                    break
                if curTrieNode.word:
                    curWord = s[start:end + 1]
                    for sentence in dp[end + 1]:
                        curSentenceList.append([curWord, *sentence])
            dp[start] = curSentenceList
        return list(map(lambda words: ' '.join(words), dp[0]))

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        word_sets = set(wordDict)
        results = []
        
        def dfs(cur_idx , cur):
            if cur_idx == len(s):
                results.append(" ".join(cur))
                return
            
            for end in range(cur_idx + 1 , len(s) + 1):
                word = s[cur_idx:end]

                if word in word_sets:
                    cur.append(word)
                    dfs(end , cur)
                    cur.pop()
            
            return
        
        dfs(0 , [])
        
        return results

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        setWordDict = set(wordDict)
        @cache
        def dfs(idx = 0):
            ret = []
            for i in range(idx + 1, len(s) + 1):
                sub = s[idx:i]
                if sub in setWordDict:
                    ret += [sub] if i == len(s) else [sub + " " + x for x in dfs(i)]
            return ret
        return dfs()

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        d = {w : i for i, w in enumerate(wordDict)}
        def dfs(idx = 0 , cur = []):
            if idx == len(s):
                return [" ".join(wordDict[i] for i in cur)]
            ret = []
            for i in range(idx+1, len(s) + 1):
                sub = s[idx:i]
                if sub in d:
                    cur.append(d[sub])
                    ret.extend(dfs(i, cur))
                    cur.pop()
            return ret
        return dfs()

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        List<String>[] mem = new List[n + 1];
        mem[0] = new ArrayList<>();
        mem[0].add("");

        for (int i = 1; i <= n; i++) {
            mem[i] = new ArrayList<>();
            for (String word: wordDict) {
                int wlen = word.length();
                if (i - wlen >= 0 && !mem[i - wlen].isEmpty() && s.substring(i-wlen, i).equals(word)) {
                    List<String> temp = new ArrayList<>();
                    for (String sentence: mem[i - wlen]) {
                        String prefix = sentence.isEmpty() ? "" : sentence + " ";
                        temp.add(prefix + word);
                    }
                    mem[i].addAll(temp);
                }
            }
        }

        return mem[n];
    }
}

public class Solution {
    public static HashSet<string> wordDictSet;
    public static List<string> result;

    public bool IsValidDictionaryWord(string s)
    {
        string[] words = s.Split(' ');
        foreach(string word in words)
        {
            if(!wordDictSet.Contains(word))
                return false;
        }
        return true;
    }

    public void BackTrack(string s, int index)
    {
        if(IsValidDictionaryWord(s))
        {
            result.Add(s);
        }
        for(int i = index; i<s.Length-1; i++)
        {
            string tempString = s.Substring(0, i + 1) + ' ' + s.Substring(i+1, s.Length - (i + 1));
            BackTrack(tempString, i+2);
        }
    }

    public IList<string> WordBreak(string s, IList<string> wordDict) {
        wordDictSet = new HashSet<string>();
        result = new List<string>();
        for(int i = 0; i<wordDict.Count; i++)
        {
            wordDictSet.Add(wordDict[i]);
        }
        BackTrack(s, 0);
        return result;
    }
}

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet(wordDict);
        List<String> res = new ArrayList<>();
        backtrack(s,dict, res, new StringBuilder(), 0);
        return res;
    }
    public void backtrack(String s, Set<String> dict,List<String> res, StringBuilder sentence, int start){
        if(start == s.length()){
            res.add(sentence.toString().trim());
            return;
        }
        for(int i=start;i<s.length();i++){
            if(dict.contains(s.substring(start, i+1))){
                sentence.append(" " + s.substring(start, i+1));
                backtrack(s, dict,res,sentence,i+1);
                sentence.delete(sentence.length()-1-(i+1-start),sentence.length());
            }
        }
    }
}

use std::collections::HashMap;

#[derive(Debug, Default)]
struct MapTrie {
    terminator: bool,
    children: HashMap<u8, MapTrie>
}

impl MapTrie {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn insert(&mut self, word: &[u8]) {
        let mut current_node = self;

        for &bc in word.into_iter() {
            current_node = current_node.children.entry(bc).or_default();
        }

        current_node.terminator = true;
    }

    pub fn contains(&self, word: &[u8]) -> bool {
        let mut current_node = self;

        for &bc in word.into_iter() {
            match current_node.get_child(bc) {
                Some(node) => current_node = node,
                None => return false,
            }
        }

        current_node.terminator
    }

    pub fn get_child(&self, bc: u8) -> Option<&Self> {
        self.children.get(&bc)
    }
}

impl Solution {
    pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
        let bytes = s.as_bytes();
        let n = bytes.len();
        let mut memo = vec![vec![-1; n]; n + 1];

        for j in 0..n {
            memo[n][j] = 1;
        }

        let mut trie = MapTrie::new();
        let mut word_length = 0;

        for word in word_dict {
            let word_bytes = word.as_bytes();
            word_length = word_length.max(word_bytes.len());
            trie.insert(word_bytes);
        }

        match Self::top_down(bytes, 0, &trie, word_length, &mut memo) {
            1 => true,
            _ => false
        }
    }

    pub fn top_down(s: &[u8], start: usize, trie: &MapTrie, word_length: usize, memo: &mut Vec<Vec<i8>>) -> i8 {
        let l = s.len();
        if start == l {
            return 1;
        }

        let mut current_node = trie;
        for i in start..((start + word_length).min(l)) {
            let bc = s[i];

            match current_node.get_child(bc) {
                Some(next_node) => {
                    current_node = next_node;

                    if !next_node.terminator {
                        continue;
                    }

                    memo[start][i] = 1;

                    if memo[i + 1][l - 1] == -1 {
                        memo[i + 1][l - 1] = Self::top_down(s, i + 1, trie, word_length, memo);
                    }

                    if memo[i + 1][l - 1] == 1 {
                        memo[start][l - 1] = 1;
                        return 1;
                    }

                    if memo[i + 1][l - 1] == 0 {
                        continue;
                    }
                },
                None => break
            }
        }

        0
    }
}

use std::collections::HashMap;

#[derive(Debug, Default)]
struct MapTrie {
    terminator: bool,
    children: HashMap<u8, MapTrie>
}

impl MapTrie {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn insert(&mut self, word: &[u8]) {
        let mut current_node = self;

        for &bc in word.into_iter() {
            current_node = current_node.children.entry(bc).or_default();
        }

        current_node.terminator = true;
    }

    pub fn contains(&self, word: &[u8]) -> bool {
        let mut current_node = self;

        for &bc in word.into_iter() {
            match current_node.get_child(bc) {
                Some(node) => current_node = node,
                None => return false,
            }
        }

        current_node.terminator
    }

    pub fn get_child(&self, bc: u8) -> Option<&Self> {
        self.children.get(&bc)
    }
}

impl Solution {
    pub fn word_break(s: String, word_dict: Vec<String>) -> Vec<String> {
        let bytes = s.as_bytes();
        let n = bytes.len();

        let mut acc: HashMap<usize, Vec<Vec<String>>> = HashMap::new();
        let mut word_len = 0;
        let mut trie = MapTrie::new();

        for word in word_dict {
            let word_bytes = word.as_bytes();
            word_len = word_len.max(word_bytes.len());
            let rev_bytes = word_bytes.into_iter().rev().map(|&bc| bc).collect::<Vec<u8>>();
            trie.insert(&rev_bytes);
        }

        let mut memo = vec![vec![-1; n]; n];

        Self::top_down(bytes, n - 1, word_len, &trie, &mut memo, &mut acc);

        acc.remove(&(n - 1)).unwrap_or(vec![]).into_iter().map(|string_vec| string_vec.join(" ")).collect()
    }

    pub fn top_down(
        s: &[u8],
        end: usize,
        word_len: usize,
        trie: &MapTrie,
        memo: &mut Vec<Vec<i8>>,
        acc: &mut HashMap<usize, Vec<Vec<String>>>
    ) -> i8 {
        let l = s.len();
        let mut lower_bound = 0;

        if end + 1 >= word_len {
            lower_bound = (end + 1) - word_len;
        }

        let mut current_node = trie;
        let mut result = 0;

        for i in (lower_bound..=end).into_iter().rev() {
            let bc = s[i];

            let option_next_node = current_node.get_child(bc);

            if option_next_node.is_none() {
                break;
            }

            let next_node = option_next_node.unwrap();
            current_node = next_node;

            if !current_node.terminator {
                continue;
            }

            memo[i][end] = 1;

            if i == 0 {
                let pushed = unsafe { std::str::from_utf8_unchecked(&s[i..=end]) }.to_owned();
                memo[0][l - 1] = 1;
                acc.entry(end).or_default().push(vec![pushed]);
                return 1;
            }

            if memo[0][i - 1] == -1 {
                memo[0][i - 1] = Self::top_down(s, i - 1, word_len, trie, memo, acc);
            }

            if memo[0][i - 1] == 1 {
                memo[i][l - 1] = 1;
                let pushed = unsafe { std::str::from_utf8_unchecked(&s[i..=end]) }.to_owned();
                let mut appended =
                    acc.get(&(i - 1)).map(|string_vecs| {
                        let mut cloned = string_vecs.clone();
                        cloned.iter_mut().for_each(|string_vec| string_vec.push(pushed.clone()));

                        cloned
                    }).unwrap();

                acc.entry(end).or_default().append(&mut appended);
                result = 1;
                continue;
            }

            if memo[0][i - 1] == 0 {
                memo[i][end] = 0;
                continue;
            }
        }

        result
    }
}

class Solution:
    def checkRecord(self, n: int) -> int:
        # dp(n, remainForLate, remainForAbsent)
        #  'L'   dp(n - 1, remainForLate - 1, remainForAbsent)
        #  'A'   dp(n - 1, remainForLate, remainForAbsent - 1)
        #  'P'   dp(n - 1, remainForLate, remainForAbsent)
        #basecase: dp(n = 0, any remainForLate, any remainForAbsent) = 1
        MOD = 10 ** 9 + 7
        maxLate = 2
        maxAbsence = 1
        prevDp = [[1] * (maxAbsence + 1) for _ in range(maxLate + 1)]
        curDp = [[0] * (maxAbsence + 1) for _ in range(maxLate + 1)]
        for i in range(1, n + 1):
            for late in range(0, maxLate + 1):
                for absence in range(0, maxAbsence + 1):
                    p = prevDp[maxLate][absence]
                    a = prevDp[maxLate][absence - 1] if absence > 0 else 0
                    l = prevDp[late - 1][absence] if late > 0 else 0
                    curDp[late][absence] = (p + a + l) % MOD
            prevDp, curDp = curDp, prevDp
        
        return prevDp[maxLate][maxAbsence]

impl Solution {
    pub fn check_record(n: i32) -> i32 {
        let un = n as usize;
        let quotient = 10i64.pow(9) + 7;
        let mut dp = vec![vec![vec![0i64; 3]; 2]; un + 1];

        dp[0][0][0] = 1;

        for len in 0..un {
            for ac in 0..=1 {
                for lc in 0..=2 {
                    dp[len + 1][ac][0] =
                        (dp[len + 1][ac][0] + dp[len][ac][lc]).rem_euclid(quotient);

                    if ac < 1 {
                        dp[len + 1][ac + 1][0] =
                            (dp[len + 1][ac + 1][0] + dp[len][ac][lc]).rem_euclid(quotient);
                    }

                    if (lc < 2) {
                        dp[len + 1][ac][lc + 1] =
                            (dp[len + 1][ac][lc + 1] + dp[len][ac][lc]).rem_euclid(quotient);
                    }
                }
            }
        }

        let mut count = 0;
        for ac in 0..=1 {
            for lc in 0..=2 {
                count = (count + dp[un][ac][lc]).rem_euclid(quotient);
            }
        }

        count as i32
    }
}