如何检查字符串是否完全由定义的子字符串组成

Question

任务

这里有一些子串：a, abb, aaaa.

如何检查输入字符串是否完全由这些子字符串组成？我想这里应该使用一些来自动态规划的算法，但我对此有点菜鸟（尤其是在动态规划方面）。

例子

check('aaaaaa') // true
check('abbaaaa') // true
check('abbab') // false, we don't have `b` substring
check('bbaaaa') // false, we don't have `bb` substring

Answer 1

已针对“断字”问题提交了相同的解决方案

https://leetcode.com/problems/word-break/discuss/1433730/Typescript-JavaScript-:-68-MS-100-40.6-MB-94.06

/* we notice that since we only need to check for a solution where we can iterate over the whole string
we dont need to create any new string but just keep track of index till where we have check for a match */
/* we can keep a dictionary to keep track of all the index, that does not result in a positive solution, eg dic */

function wordBreak(s, wordDict) {
        let failIndexDic = {}; // contains keys of failed index eg { 2: true, 5: true} 
        return loop(s, wordDict, [0], failIndexDic); // starting at zeroth index
    }
    ;
    // return the staring number of all possible strings after wd match 
    // return number same as s.length means : match found
    // returning [] is no match found 
    let brokenStrings = (startIndex, s, wd) => {
        let newStartIndexs = [];
        wd.
            forEach(word => {
            if (s.startsWith(word, startIndex))
                newStartIndexs.push(word.length + startIndex);
        });
        return newStartIndexs;
    };
    // recussive loop that should go over all values and possibilites
    // ps: possible solution staring indexs 
    // here are n are index of the string;
    // here loop taken as a node which can have multiple child in form of PS
    let loop = (s, wd, ps, dic) => {
        if (ps.length === 0)
            return false; // no match found
        if (ps.some(n => n === s.length))
            return true; // full iteration has happened
        // depth first loop
        return ps.some(n => {
            let nArr = brokenStrings(n, s, wd);
            nArr = nArr.filter(n => !dic[n]); // remove previusly failed indexs
            let hasMatch = loop(s, wd, nArr, dic);
            if (!hasMatch)
                nArr.forEach(n => dic[n] = true); // add latest failed indexs to failed dictionary
            return hasMatch; // once true it will not check for remaining ps values
        });
    };

console.log([wordBreak('bbaaaa', ['a', 'abb', 'aaaa']),
wordBreak('abbaaaa', ['a', 'abb', 'aaaa']),
wordBreak('abbab', ['a', 'abb', 'aaaa'])])

如何检查字符串是否完全由定义的子字符串组成

How can I check string entirely is made up of defined substrings

javascript

algorithm

dynamic-programming