Bảng băm

127. Chuỗi từ chuyển đổi

Bài toán

Từ điển wordList chứa một chuỗi từ beginWord đến endWord với dãy chuyển đổi được tạo theo các quy tắc sau: beginWord -> s(1) -> s(2) -> ... -> s(k):

• Mỗi cặp từ kề nhau chỉ khác nhau bởi một ký tự.
• Đối với 1 <= i <= k, mỗi s(i) đều nằm trong wordList. Lưu ý rằng, beginWord không cần phải có trong wordList.
• s(k) == endWord

Cho hai từ beginWord và endWord cùng với từ điển wordList, hãy trả về số lượng từ trong dãy chuyển đổi ngắn nhất từ beginWord đến endWord. Nếu không tồn tại dãy như vậy, trả về 0.

/**
 * @param {string} start
 * @param {string} target
 * @param {string[]} dict
 * @return {number}
 */
var shortestTransformation = function (start, target, dict) {
    if (!dict.includes(target)) return 0;
    let wordSet = new Set(dict);
    let queue = [[start, 1]];
    
    while (queue.length > 0) {
        let [current, steps] = queue.shift();
        if (current === target) return steps;
        
        for (let i = 0; i < current.length; i++) {
            for (let charCode = 97; charCode <= 122; charCode++) {
                let nextWord = current.slice(0, i) + String.fromCharCode(charCode) + current.slice(i + 1);
                if (wordSet.has(nextWord)) {
                    queue.push([nextWord, steps + 1]);
                    wordSet.delete(nextWord);
                }
            }
        }
    }
    return 0;
};

140. Phân tách từ II

Bài toán

Cho một chuỗi text và một danh sách từ vocab, hãy chèn dấu cách vào chuỗi text để tạo thành câu sao cho tất cả các từ đều xuất hiện trong từ điển. Trả về tất cả các khả năng phân tách theo thứ tự tùy chọn.

/**
 * @param {string} text
 * @param {string[]} vocab
 * @return {string[]}
 */
var splitWords = function (text, vocab) {
    const memo = new Map();
    const wordSet = new Set(vocab);

    function backtrack(index) {
        if (memo.has(index)) return memo.get(index);
        if (index === text.length) return [[]];

        let results = [];
        for (let i = index + 1; i <= text.length; i++) {
            let prefix = text.slice(index, i);
            if (wordSet.has(prefix)) {
                let suffixes = backtrack(i);
                for (let suffix of suffixes) {
                    results.push([prefix].concat(suffix));
                }
            }
        }
        memo.set(index, results);
        return results;
    }

    return backtrack(0).map(sent => sent.join(' '));
};

383. Tín phiếu chuộc tội

Bài toán

Kiểm tra xem chuỗi note có thể được tạo ra từ các ký tự của chuỗi source hay không. Mỗi ký tự trong source chỉ được sử dụng một lần.

/**
 * @param {string} note
 * @param {string} source
 * @return {boolean}
 */
var canBuildNote = function (note, source) {
    let countMap = {};
    for (let char of source) {
        countMap[char] = (countMap[char] || 0) + 1;
    }
    for (let char of note) {
        if (!countMap[char]) return false;
        countMap[char]--;
    }
    return true;
};

2103. Vòng và que

Bài toán

Có n vòng màu đỏ, xanh lá hoặc xanh dương được đặt trên 10 que đánh số từ 0 đến 9. Hãy tìm số que mà trên đó có đủ cả ba màu vòng.

/**
 * @param {string} rings
 * @return {number}
 */
var countCompleteRods = function (rings) {
    let rodStatus = Array(10).fill(0);
    for (let i = 0; i < rings.length; i += 2) {
        let color = rings[i];
        let rod = rings[i + 1];
        switch (color) {
            case 'R': rodStatus[rod] |= 1; break;
            case 'G': rodStatus[rod] |= 2; break;
            case 'B': rodStatus[rod] |= 4; break;
        }
    }
    return rodStatus.filter(status => status === 7).length;
};

2744. Số cặp chuỗi tối đa

Bài toán

Tìm số cặp tối đa giữa các từ trong mảng words sao cho một từ là phiên bản đảo ngược của từ kia.

/**
 * @param {string[]} words
 * @return {number}
 */
var maxMatchingPairs = function (words) {
    let seen = new Set();
    let pairs = 0;
    for (let word of words) {
        let reversed = word.split('').reverse().join('');
        if (seen.has(reversed)) {
            pairs++;
            seen.delete(reversed);
        } else {
            seen.add(word);
        }
    }
    return pairs;
};

3158. XOR của các số xuất hiện hai lần

Bài toán

Trả về giá trị XOR của tất cả các số xuất hiện hai lần trong mảng nums.

/**
 * @param {number[]} nums
 * @return {number}
 */
var xorOfDuplicates = function (nums) {
    let counts = {};
    for (let num of nums) {
        counts[num] = (counts[num] || 0) + 1;
    }
    let result = 0;
    for (let [num, freq] of Object.entries(counts)) {
        if (freq === 2) result ^= num;
    }
    return result;
};