[902] Numbers At Most N Given Digit Set

[tsungtingdu]

遞迴解，Time Limit Exceeded

var atMostNGivenDigitSet = function(digits, n) {
    let set = new Set()
    let length = String(n).length
    traverse([], digits) 

    return set.size

    function traverse(cur, digits) {
        if (cur.length > length) return

        let num = Number(cur.join(''))
        if (num <= n && num !== 0) set.add(num)

        for (let i = 0; i < digits.length; i++) {
            cur.push(digits[i])
            traverse([...cur], digits)
            cur.pop()
        }
    }
};

DP 參考解

var atMostNGivenDigitSet = function(digits, n) {
    let str = String(n)
    let ans = 0

    for (let i = 0; i < str.length - 1; i++) {
        ans += Math.pow(digits.length, i + 1)
    }

    for (let i = 0; i < str.length; i++) {
        let check = false
        for (let j = 0; j < digits.length; j++) {
            if (digits[j] < str[i]) {
                ans += Math.pow(digits.length, str.length - i - 1)
            } else if (digits[j] === str[i]) {
                check = true
                break
            }
        }
        if (!check) return ans
    }
    return ans + 1
};

[harrytothemoon]

直覺排列組合解 分兩部分 先判斷小於目標位數的排列組合 在判斷等於目標位數的排列組合 在第二部分有點卡住，參考了T4寫的check作法

var atMostNGivenDigitSet = function(digits, n) {
    let len = digits.length
    let res = 0
    let digit = 1
    let targetDigit = String(n).length
    while (digit < targetDigit) {
        res += Math.pow(len, digit)
        digit++
    }
    for (let i = 0; i < targetDigit; i++) {
        let check = false
        for (let j = 0; j < len; j++) {
            if (digits[j] < String(n)[i]) {
                res += Math.pow(len, targetDigit - (i + 1))
            } else if (digits[j] === String(n)[i]) {
                check = true
                break
            }
        }
        if (!check) return res
    }
    return res + 1
};

[windate3411]

參考解，分成三部份處理

1. 位數小於目標數字長度的組合，這個較為直覺簡單，困難的在第二、三步，卡關
2. 位數等於目標數字長度的組合，迭代每個目標數字，檢查digits陣列內可用來排列的數字並進行排列組數計算
3. 處理排列數字恰巧等於目標數字的情況

var atMostNGivenDigitSet = function(digits, n) {
    n = String(n)
    const len = n.length
    let result = 0
    countNumsLessDigitThanN()
    countNumsSameDigitAsN()
    return result
    // 第一部分
    function countNumsLessDigitThanN() {
        for (let i = 1; i < len; i++) {
            result += Math.pow(digits.length, i)
        }
    }
     // 第二部分
    function countNumsSameDigitAsN() {
        for (let i = 0; i < len; i++) {
            const properDigits = digits.filter(num => num < n[i])
            result += properDigits.length * Math.pow(digits.length, len - i - 1)

            // 第三部分
            if (!digits.includes(n[i])) break
            if (i === len - 1 )  result += 1
        }
    }
};