Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
6
Indexable
const recursion = (source, currentString, index, min, lambda) => {
    if (index === source.length) {
        // console.log('end', lambda, currentString)
        if (lambda != 0) {
            return { min, list: [] }
        } else {
            return { min, list: [currentString] }
        }
    }

    const char = source[index]
    if (!'()'.includes(char)) return recursion(source, currentString + char, index + 1, min, lambda)

    // get this char
    let getLambda = lambda
    if (char === '(') getLambda++
    else if (char === ')') getLambda--

    let minGet = source.length
    let listGet = []
    if (getLambda >= 0) {
        // console.log('getting', index, currentString, char, 'getLambda', getLambda, min);
        ({ min: minGet, list: listGet } = recursion(source, currentString + char, index + 1, min, getLambda));
        // console.log('minGet', index, minGet, listGet);
    }

    // skip this char
    // console.log('skipping', index, currentString, char, 'lambda', lambda, min)
    const { min: minSkip, list: listSkip } = recursion(source, currentString, index + 1, min + 1, lambda)
    // console.log('minSkip', index, minSkip, listSkip)

    const list = []

    let currentMin = source.length
    if (listSkip.length > 0) currentMin = minSkip
    if (listGet.length > 0) currentMin = Math.min(currentMin, minGet)

    // console.log('check min', minGet, listGet, minSkip, listSkip, 'xxx', currentMin)

    if (minGet === currentMin && listGet.length > 0) list.push(...listGet)
    if (minSkip === currentMin && listSkip.length > 0) list.push(...listSkip)
    // console.log('check min done', list)

    return {
        min: currentMin,
        list,
    }
}

/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function(s) {
    const a = recursion(s, "", 0, 0, 0)
    // console.log(a.list)
    const uniqueItems = [...new Set(a.list)]
    if (uniqueItems.length === 0) return [""]
    return uniqueItems;
};