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

class Solution {
private:
    vector<vector<char>> table = {
        {'a', 'b', 'c'},
        {'d', 'e', 'f'},
        {'g', 'h', 'i'},
        {'j', 'k', 'l'},
        {'m', 'n', 'o'},
        {'p', 'q', 'r', 's'},
        {'t', 'u', 'v'},
        {'w', 'x', 'y', 'z'},
    };
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return {};
        vector<string> res = {""};
        for(char c : digits){
            vector<string> tmp;
            for(char ch : table[c - '0' - 2])
                for(string s : res) tmp.push_back(s + ch);
            res = tmp;
        }
        return res;
    }
};

var letterCombinations = function(digits) {
    const numberPhone = {
        0: [],
        1: [],
        2: ['a', 'b', 'c'],
        3: ['d', 'e', 'f'],
        4: ['g', 'h', 'i'],
        5: ['j', 'k', 'l'],
        6: ['m', 'n', 'o'],
        7: ['p', 'q', 'r', 's'],
        8: ['t', 'u', 'v'],
        9: ['w', 'x', 'y', 'z']
      };
      const Array =[]
      function Try(s){
        if(s.length==digits.length){
            Array.push(s);
        }
        else {
            for (let i = 0; i < numberPhone[parseInt(digits[s.length])].length; i++) {
                Try(s+numberPhone[parseInt(digits[s.length])][i])
            }
        }
      }
      Try("")
      
      if(Array[0]==''){
        return []
      }
      else{

          return Array
      }

};

var letterCombinations = function(digits) {
    if (!digits) {
        return [];
    }
    const km = {
        2: 'abc', 3: 'def',
        4: 'ghi', 5: 'jkl', 6: 'mno',
        7: 'pqrs', 8: 'tuv', 9: 'wxyz',
    }
    const ans = [];
    const backtrack = (prefix, digs) => {
        const isLast = digs.length === 1;
        for (const ch of km[digs[0]]) {
            if (isLast) {
                ans.push(prefix + ch);
            } else {
                backtrack (prefix + ch, digs.slice(1));
            }
        }
    }
    backtrack('', digits);
    
    return ans;
};

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        mapDigitChar = {
            "2": 'abc',
            "3": 'def',
            "4": 'ghi',
            "5": 'jkl',
            "6": 'mno',
            "7": 'pqrs',
            "8": 'tuv',
            "9": 'wxyz',
        }
        res = []

        if len(digits) == 0:
            return res
        
        def backtrack(curIdx: int, combination: List[str]):
            if len(combination) == len(digits):
                res.append(''.join(combination))
                return

            for i in range(curIdx, len(digits)):
                for char in mapDigitChar[digits[i]]:
                    combination.append(char)
                    backtrack(i+1, combination[:])
                    combination.pop()
        
        backtrack(0, [])

        return res

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        data = {
            2 : "abc",
            3 : "def",
            4 : "ghi",
            5 : "jkl",
            6 : "mno",
            7 : "pqrs",
            8 : "tuv",
            9 : "wxyz"
        }
        res = []
        def dfs(i , s):
            if len(s) == len(digits):
                res.append(s)
                return
            for digit in data[int(digits[i])]:
                dfs(i + 1 , s + digit)
        dfs(0 , "")
        if res[0] == "": res.clear()
        return res

struct Solution {
    vector<string> letterCombinations(string_view digits) {
        vector<string> res(!digits.empty());
        for (char dg : digits) {
            vector<string> tmp;
            for (char len = (dg == '9' || dg == '7') + 3, ch = 'a' + 3 * (dg - '2') + (dg >= '8'); len--; ++ch)
                transform(begin(res), end(res), back_inserter(tmp), [ch](const auto& s){ return s + ch; });
            swap(res, tmp);
        }
        return res;
    }
};

class TrieNode:
    def __init__(self):
        self.is_end = False
        self.next = dict()


class Trie:
    def __init__(self):
        self.root = TrieNode()
   
    def add_word(self, word):
        current_node = self.root

        for char in word:
            if char not in current_node.next:
                current_node.next[char] = TrieNode()
            current_node = current_node.next[char]
       
        current_node.is_end = True

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        trie = Trie()
        for word in wordDict:
            trie.add_word(word)
       
        dp = [False for _ in range(n)]

        for current_index in range(n):
            if current_index > 0 and dp[current_index - 1] == False:
                continue
           
            current_node = trie.root

            while current_index < n:
                current_char = s[current_index]
                if current_char not in current_node.next:
                    break
                current_node = current_node.next[current_char]
                dp[current_index] = max(dp[current_index], current_node.is_end)
                current_index += 1
           
        return dp[n - 1]