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

Tại sao cái này là không phải valid binary search tree nhỉ, mình vẫn chưa hiểu.


1716542047595.png
 
một con gà ngồi debug =((

Code: 
impl Solution {
    pub fn max_score_words(words: Vec<String>, letters: Vec<char>, letter_scores: Vec<i32>) -> i32 {
        let n = words.len();
        let mut word_letter_freqs: Vec<Vec<i32>> = vec![vec![0i32; 26]; n];

        for (i, word) in words.into_iter().enumerate() {
            for &bc in word.as_bytes().into_iter() {
                word_letter_freqs[i][(bc - b'a') as usize] += 1;
            }
        }

        let mut letter_freqs = vec![0i32; 26];
        for c in letters.into_iter() {
            letter_freqs[((c as u8) - b'a') as usize] += 1;
        }

        Self::backtrack(
            &word_letter_freqs,
            &mut letter_freqs,
            &letter_scores,
            0
        )
    }

    pub fn backtrack(
        rem_word_letter_freqs: &[Vec<i32>],
        letter_freqs: &mut Vec<i32>,
        letter_scores: &Vec<i32>,
        score: i32
    ) -> i32
    {
        let l = rem_word_letter_freqs.len();

        if l == 0 {
            return score;
        }

        let mut max_score = score;

        for i in 0..l {
            let word_letter_freqs = &rem_word_letter_freqs[i];
            let mut should_call = true;
            let mut prop_score = score;

            for j in 0..26 {
                letter_freqs[j] -= word_letter_freqs[j];
                prop_score += letter_scores[j] * word_letter_freqs[j];

                should_call = should_call && (letter_freqs[j] >= 0);
            }

            if should_call {
                let new_score =
                    Self::backtrack(
                        &rem_word_letter_freqs[(i + 1)..],
                        letter_freqs,
                        letter_scores,
                        prop_score
                    );

                max_score = max_score.max(new_score);
            }

            for j in 0..26 {
                letter_freqs[j] += word_letter_freqs[j];
            }

            let new_score =
                Self::backtrack(
                    &rem_word_letter_freqs[(i + 1)..],
                    letter_freqs,
                    letter_scores,
                    score
                );

            max_score = max_score.max(new_score);
        }

        max_score
    }
}

Code: 
impl Solution {
    pub fn max_score_words(words: Vec<String>, letters: Vec<char>, letter_scores: Vec<i32>) -> i32 {
        let n = words.len();
        let mut word_letter_freqs: Vec<Vec<i32>> = vec![vec![0i32; 26]; n];

        for (i, word) in words.into_iter().enumerate() {
            for &bc in word.as_bytes().into_iter() {
                word_letter_freqs[i][(bc - b'a') as usize] += 1;
            }
        }

        let mut letter_freqs = vec![0i32; 26];
        for c in letters.into_iter() {
            letter_freqs[((c as u8) - b'a') as usize] += 1;
        }

        Self::backtrack(
            &word_letter_freqs,
            &mut letter_freqs,
            &letter_scores,
            0
        )
    }

    pub fn backtrack(
        rem_word_letter_freqs: &[Vec<i32>],
        letter_freqs: &mut Vec<i32>,
        letter_scores: &Vec<i32>,
        score: i32
    ) -> i32
    {
        let l = rem_word_letter_freqs.len();

        if l == 0 {
            return score;
        }

        let mut max_score = score;

        for i in 0..l {
            let word_letter_freqs = &rem_word_letter_freqs[i];
            let mut should_call = true;
            let mut prop_score = score;

            for j in 0..26 {
                letter_freqs[j] -= word_letter_freqs[j];
                prop_score += letter_scores[j] * word_letter_freqs[j];

                should_call = should_call && (letter_freqs[j] >= 0);
            }

            if should_call {
                let new_score =
                    Self::backtrack(
                        &rem_word_letter_freqs[(i + 1)..],
                        letter_freqs,
                        letter_scores,
                        prop_score
                    );

                max_score = max_score.max(new_score);
            }

            for j in 0..26 {
                letter_freqs[j] += word_letter_freqs[j];
            }
        }

        max_score
    }
}

Code: 
impl Solution {
    pub fn max_score_words(words: Vec<String>, letters: Vec<char>, letter_scores: Vec<i32>) -> i32 {
        let n = words.len();
        let mut letter_freqs = vec![0i32; 26];
        for c in letters.into_iter() {
            letter_freqs[((c as u8) - b'a') as usize] += 1;
        }

        Self::backtrack(&words, &mut letter_freqs, &letter_scores, 0)
    }

    pub fn backtrack(
        rem_words: &[String], letter_freqs: &mut Vec<i32>, letter_scores: &Vec<i32>, score: i32
    ) -> i32
    {
        let l = rem_words.len();

        if l == 0 {
            return score;
        }

        let mut max_score = score;
        for i in 0..l {
            let word = &rem_words[i];
            let mut should_call = true;
            let mut prop_score = score;

            for &bc in word.as_bytes().iter() {
                let index = (bc - b'a') as usize;
                letter_freqs[index] -= 1;
                prop_score += letter_scores[index];
                should_call = should_call && (letter_freqs[index] >= 0);
            }

            if should_call {
                let new_score =
                    Self::backtrack(&rem_words[(i + 1)..], letter_freqs, letter_scores, prop_score);
                max_score = max_score.max(new_score);
            }

            for &bc in word.as_bytes().iter() {
                let index = (bc - b'a') as usize;
                letter_freqs[index] += 1;
            }
        }

        max_score
    }
}
 
Last edited:
small-lambda said:
một con gà ngồi debug =((

Code: 
impl Solution {
    pub fn max_score_words(words: Vec<String>, letters: Vec<char>, letter_scores: Vec<i32>) -> i32 {
        let n = words.len();
        let mut word_letter_freqs: Vec<Vec<i32>> = vec![vec![0i32; 26]; n];

        for (i, word) in words.into_iter().enumerate() {
            for &bc in word.as_bytes().into_iter() {
                word_letter_freqs[i][(bc - b'a') as usize] += 1;
            }
        }

        let mut letter_freqs = vec![0i32; 26];
        for c in letters.into_iter() {
            letter_freqs[((c as u8) - b'a') as usize] += 1;
        }

        Self::backtrack(
            &word_letter_freqs,
            &mut letter_freqs,
            &letter_scores,
            0
        )
    }

    pub fn backtrack(
        rem_word_letter_freqs: &[Vec<i32>],
        letter_freqs: &mut Vec<i32>,
        letter_scores: &Vec<i32>,
        score: i32
    ) -> i32
    {
        let l = rem_word_letter_freqs.len();

        if l == 0 {
            return score;
        }

        let mut max_score = score;

        for i in 0..l {
            let word_letter_freqs = &rem_word_letter_freqs[i];
            let mut should_call = true;
            let mut prop_score = score;

            for j in 0..26 {
                letter_freqs[j] -= word_letter_freqs[j];
                prop_score += letter_scores[j] * word_letter_freqs[j];

                should_call = should_call && (letter_freqs[j] >= 0);
            }

            if should_call {
                let new_score =
                    Self::backtrack(
                        &rem_word_letter_freqs[(i + 1)..],
                        letter_freqs,
                        letter_scores,
                        prop_score
                    );

                max_score = max_score.max(new_score);
            }

            for j in 0..26 {
                letter_freqs[j] += word_letter_freqs[j];
            }

            let new_score =
                Self::backtrack(
                    &rem_word_letter_freqs[(i + 1)..],
                    letter_freqs,
                    letter_scores,
                    score
                );

            max_score = max_score.max(new_score);
        }

        max_score
    }
}
Click to expand...
Viết dài quá sẽ khó debug, viết 1 line thì bị Vozers chửi :shame:

via theNEXTvoz for iPhone
 
Bài này medium thôi còn ko tới medium hard nữa ấy chứ
Python: 
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordSet = set(wordDict)
        words = []
        def dp(index, currentWord):
            if index == len(s):
                words.append(currentWord)

            for i in range(index, len(s)):
                word = s[index: i + 1]
                if word in wordSet:
                    nextWord = word if currentWord == "" else currentWord + " " + word
                    dp(i + 1, nextWord)

        dp(0, "")
        return words
 
freedom.9 said:
Bài này medium thôi còn ko tới medium hard nữa ấy chứ
Python: 
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordSet = set(wordDict)
        words = []
        def dp(index, currentWord):
            if index == len(s):
                words.append(currentWord)

            for i in range(index, len(s)):
                word = s[index: i + 1]
                if word in wordSet:
                    nextWord = word if currentWord == "" else currentWord + " " + word
                    dp(i + 1, nextWord)

        dp(0, "")
        return words
Click to expand...
T nghĩ bài này dễ là do cái S ngắn quá (<=20). Nên k cần setup gì đặc biệt vẫn pass. Cho dài tí là phải setup cái trie để search thì mới pass đc, lúc đó sẽ khó hơn chút
 
seastar said:
T nghĩ bài này dễ là do cái S ngắn quá (<=20). Nên k cần setup gì đặc biệt vẫn pass. Cho dài tí là phải setup cái trie để search thì mới pass đc, lúc đó sẽ khó hơn chút
Click to expand...
Đúng rồi xài trie optimize tí như bài word break cũng được. Mình lúc đầu làm cũng bất ngờ là xài set beat cả đống luôn.

via theNEXTvoz for iPhone
 
Java: 
fun wordBreak(s: String, wordDict: List<String>): List<String> {
        val dp = Array(s.length) { mutableListOf<String>() }
        for (i in s.indices) {
            val sub = s.substring(0, i + 1)
            for (word in wordDict) {
                if (sub == word) {
                    dp[i].add(word)
                } else if (sub.endsWith(word)) {
                    for (sentence in dp[i - word.length]) {
                        dp[i].add("$sentence $word")
                    }
                }
            }
        }
        return dp.last()
    }
 
Này build dictionary words để duyệt string nhanh hơn. Ví dụ "cat" => dict = ["c":false, "ca":false, "cat":true]
- "cat" => duyệt "c", "ca", "cat" => valid word
- "cats" => duyệt "c", "ca", "cat":
1. "cat" => valid word, thêm " ", dfs duyệt tiếp "cat s": "s" không có trong dict => invalid
2. duyệt "cats" => invalid
Thấy vẫn chưa tối ưu lắm, tốn effort build dict.

Swift: 
class Solution {
    func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
     
       // Build dict...
        var dict:[[Character]:Bool] = [:]
        for str in wordDict {
            let chars = [Character](str)
            if chars.count > 1 {
                for num in 1...chars.count-1 {
                    let subChars = Array(chars[0..<num])
                    dict[subChars] = false
                }
            }
        }
        for str in wordDict {
            let chars = [Character](str)
            dict[chars] = true
        }
     
       // Check s
        var res:[[Character]] = []
      
        func dfs(c: [Character], i: Int) {
            var l = 1
            while (i+l <= c.count) {
                let subC = Array(c[i..<i+l])
                if let isWord = dict[subC] {
                    if isWord {
                        if (i+l) == c.count {
                            res.append(c)
                            break
                        }
                        var newChars = c
                        newChars.insert(" ", at: i+l)
                        dfs(c: newChars, i: i+l+1)
                    }
                    l += 1
                } else {
                    break
                }
            }
        }

        dfs(c: [Character](s), i: 0)

        return res.map { String($0) }
    }
}
 
seastar said:
T nghĩ bài này dễ là do cái S ngắn quá (<=20). Nên k cần setup gì đặc biệt vẫn pass. Cho dài tí là phải setup cái trie để search thì mới pass đc, lúc đó sẽ khó hơn chút
Click to expand...
hashmap O(1) rồi setup trie làm gì nữa bác
 
GD-Cuong said:
hashmap O(1) rồi setup trie làm gì nữa bác
Click to expand...
Trie để early termination bác.
Ví dụ như bác dùng set thì chỉ chứa các từ có 3 kí tự chả hạn vd "abc", "aed". Mà bác đang backtrack ở 2 kí tự vd "df" thì bác phải đi tới kí tự thứ 3 để chắc chắn là trong set ko tồn tại cái chuỗi "dfg" cần tìm.
Nhưng mà nếu dùng trie thì ngay từ chữ "d" đầu tiên thì bác đã biết là ko có từ nào bắt đầu bằng "d" trong trie cả và break backtracking luôn.

via theNEXTvoz for iPhone
 
Python: 
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        wordHash = {}
        for word in wordDict:
            wordHash[word] = True
        
        def innerWordBreak(s, start_idx, current_idx):
            result = []
            cur = s[start_idx:current_idx]
            if cur in wordHash:
                if current_idx == len(s):
                    result.append(cur)
                else:
                    result1 = innerWordBreak(s, current_idx, current_idx + 1)
                    for tmp in result1:
                        result.append(cur + " " + tmp)
          
            if current_idx == len(s):
                return result
            else:
                result2 = innerWordBreak(s, start_idx, current_idx + 1)
                return result + result2

        return innerWordBreak(s, 0, 1)
 
Python: 
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        result, n = [], len(s)
        wordSet = set(wordDict)

        def backtracking(i, current):
            if i == n:
                result.append(" ".join(current))

            for j in range(i, n):
                if s[i:j+1] in wordSet:
                    current.append(s[i:j+1])
                    backtracking(j + 1, current)
                    current.pop()

        backtracking(0, [])
        return result
 
freedom.9 said:
Trie để early termination bác.
Ví dụ như bác dùng set thì chỉ chứa các từ có 3 kí tự chả hạn vd "abc", "aed". Mà bác đang backtrack ở 2 kí tự vd "df" thì bác phải đi tới kí tự thứ 3 để chắc chắn là trong set ko tồn tại cái chuỗi "dfg" cần tìm.
Nhưng mà nếu dùng trie thì ngay từ chữ "d" đầu tiên thì bác đã biết là ko có từ nào bắt đầu bằng "d" trong trie cả và break backtracking luôn.

via theNEXTvoz for iPhone
Click to expand...
8-) à đúng rồi bác
Bị chấp niệm với cái worst case quá
 

Similar threads

Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
612
heocon0123
heocon0123
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
151
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
16
Views
414
truonggiang!
T
@_shin
kiến thức PIXELVERSE kèo hot - inbox tele để lấy extension chạy auto đánh boss
Replies
0
Views
125
@_shin
@_shin
D
kiến thức Lộ trình tự học phát triển Website Fullstack - Fullstack Web Development
2
Replies
25
Views
2K
Kieft
Kieft

Share this page

Back
Top