One possible approach is to check for each prefix whether it can be expressed using the input strings.
The idea is that if we can easily compute whether the prefix with length i can be expressed with the input strings, if we already have this information for shorter prefixes (this can be done by checking whether any of the allowed strings lead to a shorter expressible prefix) -- see code below.
var str = "forthcarkeys";
var arr = ["for","car","keys","forth"];
// isPossible[i] indicates whether we can express the
// prefix str.substring(0, i) using strings in arr.
var isPossible = Array(str.length + 1).fill(false);
// it is always possible to construct the empty string
isPossible[0] = true;
// consider each prefix of str, from shortest to longest
for (var i = 1; i <= str.length; i++) {
// try to reach this prefix using an allowed string s_allowed,
// by appending s_allowed to a shorter prefix
for (var j = 0; j < arr.length; j++) {
// "start" is the position where the current string
// would need to be appended
start = i - arr[j].length;
if (start >= 0 && isPossible[start]) {
if (str.substring(start, i) == arr[j]) {
isPossible[i] = true;
// we break the loop over j, because we already found a
// solution to express the current prefix str.substring(0,i)
break;
}
}
}
}
for (var i = 1; i <= str.length; i++) {
console.log(str.substring(0, i) + " - " + isPossible[i] + "\n")
}
if (isPossible[str.length]) {
console.log("yes");
} else {
console.log("no");
}
To further detail how this works, consider a smaller example:
- str = "abcd"
- arr = ["ab", "a", "cd"]
The approach described here tests all prefixes of str, in increasing order of their length:
Step 0: empty prefix -- this is considered as always fine (it can be expressed using 0 strings).
Step 1: prefix "a":
We try reaching this prefix using a shorter prefix + one allowed string. To do so, we iterate through the allowed strings:
- "ab" can not be appended to a shorter prefix in order to get "a" (because the start position would need to be -1).
- "a" can be appended to the empty prefix, which is always fine -- thus we get that prefix "a" is fine (can be expressed using the allowed strings).
Step 2: prefix "ab":
We try reaching this prefix using a shorter prefix + one allowed string. To do so, we iterate through the allowed strings:
- "ab" can be appended to the empty prefix, which is always fine -- thus we get that prefix "ab" is fine (can be expressed using the allowed strings).
Step 3: prefix "abc":
We try reaching this prefix using a shorter prefix + one allowed string. To do so, we iterate through the allowed strings:
- "ab" -- to append this one to a shorter prefix and get the current "abc" prefix, we would need to start at position 1, but the substring from that start position is "bc", thus we can not append the string "ab" to get prefix "abc".
- "a" -- similar to above, we can not append "a" to get prefix "abc".
- "cd" -- similar to above, we can not append "cd" to get prefix "abc".
We exhausted all allowed strings, thus prefix "abc" can not be expressed using the allowed strings.
Step 4: prefix "abcd" (entire string):
We try reaching this prefix using a shorter prefix + one allowed string. To do so, we iterate through the allowed strings:
- "ab" -- to append this one to a shorter prefix and get the current "abcd" prefix, we would need to start at position 2, but the substring from that start position is "cd", thus we can not append the string "ab" to get prefix "abcd".
- "a" -- similar to above, we can not append "a" to get prefix "abcd".
- "cd" -- we can append this allowed string to the "ab" prefix. In a previous step we found out that the "ab" prefix is fine (can be expressed with given strings), thus it is fine to append "cd" from there.
Thus, we get that the prefix "abcd" (which corresponds to the entire string) can be expressed using the input strings.
arr = [ "abcd", "def", "abc" ]andstr = "abcdef"