Check if a string is a combination of strings in an array using javascript
I have a requirement to check if a string is formed with any combination of strings given in the array For example: we have an array of ["for", "car", "keys", "forth"] and the string "fourcarkeys", the result should be true. If the string is the "fourth key", the result should be false since xy is not in the array. The order of the words in the array doesn't matter. it is not necessary that all the strings from the array be matched, but the teststring should only be made from any of the strings in the array. If it contains any string other than the one in the array, return false
my approach:
var str = "forthcarkeys";
var arr = ["for","car","keys","forth"];
for(var i=0;i<arr.length;i++)
{
if(str.indexOf(arr[i]) !== -1)
{
str.replace(arr[i],"");
}
}
if(str !== "")
{
console.log("yes");
} else
{
console.log("no");
}
but this approach is ineffective and doesn't work.
source to share
One possible approach is to check for each prefix to see if it can be expressed using the input strings.
The idea is that if we can easily figure out if a prefix with length i can be expressed with input strings if we already have this information for shorter prefixes (this can be done by checking if any of the valid strings will result in a shorter expressive 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");
}
For more details on how this works, consider a smaller example:
- str = "abcd"
- arr = ["ab", "a", "cd"]
The approach described here checks all str prefixes in ascending order of length:
Step 0: empty prefix - this is always fine (can be expressed with 0 lines).
Step 1: prefix "a":
We are trying to achieve this prefix using a shorter prefix + one valid string. To do this, we iterate over the allowed lines:
- "ab" cannot be appended to a shorter prefix to get "a" (because the start position must be -1).
- "a" can be added to an empty prefix, which is always fine, so we get that "a" is fine (can be expressed using valid strings).
Step 2: prefix "ab":
We are trying to achieve this prefix using a shorter prefix + one valid string. To do this, we iterate over the allowed lines:
- "ab" can be appended to empty prefixes, which is always fine, so we get that "ab" is fine (can be expressed with legal strings).
Step 3: prefix "abc":
We are trying to achieve this prefix using a shorter prefix + one valid string. To do this, we iterate over the allowed lines:
- "ab" - add this code to the shorter prefix and get the current prefix "abc", we will need to start from position 1, but the substring from this starting position is "bc", so we cannot add the string "ab" to get prefix "abc".
- "a" - similar to above, we cannot add "a" to get the "abc" prefix.
- "cd" - similar to above, we cannot add "cd" to get the "abc" prefix.
We have exhausted all valid strings, so the "abc" prefix cannot be expressed using valid strings.
Step 4: prefix "abcd" (whole string):
We are trying to achieve this prefix using a shorter prefix + one valid string. To do this, we iterate over the allowed lines:
- "ab" - add this code to the shorter prefix and get the current prefix "abcd", we will need to start at position 2, but the substring from this starting position is "cd", so we cannot add the string "ab" to get the prefix "abcd".
- "a" - similar to above, we cannot add "a" to get the "abcd" prefix.
- "cd" - we can add this valid string to the "ab" prefix. In the previous step, we figured out that the "ab" prefix is exact (can be expressed with given strings), so it's fine to add "cd" from there.
Thus, we get that the prefix "abcd" (which matches the entire string) can be expressed using the input strings.
source to share
you need an sort
array by length Dec
order and change if condition for yes
isstr==""
function check(str){
var arr = ["for", "car", "keys", "forth"];
arr= arr.sort((a,b)=> b.length-a.length) // sort with length dec order
console.log(arr) //longest length string is first then to lower length
for (var i = 0; i < arr.length; i++) {
str = str.replace(arr[i], "");
}
if (str.trim()== "") { //empty
console.log("yes");
} else {
console.log("no");
}
}
check("forthcarkeys")
check("forthcarxykeys")
source to share
If all words match first, unused words cannot be omitted at the beginning. Then, if the matches match the order of occurrence in the string, recursion can be used to find all matches after the match:
function eval(str, wordList = ["for","car","keys","forth", "the"]){ //note, added 'the' for testing
if(!str)return false; //empty string -> false
const words = wordList.map(w=> ({word:w, index: str.indexOf(w)})) //map all words with their occurence index inside the string
.filter(w=>w.index !== -1) //get rid of non occuring words alltogether
.sort((w1,w2) => w1.index - w2.index); //sort by index of occurence
const check = (arr,ind) => {
if(ind>=str.length)return ind === str.length; //end of string reached -> match if exactly at end (false if greater than)
let w;
while(arr.length){
[w,...arr] = arr; //destructure: w = next word (index 0), arr is set to the remaining elements
if(w.index > ind) return false; //gap since last match -> no match
if(w.index===ind && check(arr,ind + w.word.length)) //if match is at the expected index, check the next indices
return true; //word started at the 'current' index and remaining words match as well
//if code arrives here, try further with next word (while)
}
return false;
};
return check(words,0); //start recursive function with all words at string index 0
}
//test
function test(str, words){
console.log(str,':', eval(str, words));
}
test("forthcarkeys");
test("forthcarxykeys");
test("forthecar");
test("abcdef",[ "abc", "def", "abcd" ]);
source to share
You can do an extended try and search for each word and use the temporary result set to filter if the words are in the string.
function check(string, array) {
function fork(i, t) {
var s = t.slice(), j;
if (i === possibilities.length) {
result.push(t.join(''));
return;
}
if (possibilities[i].word.split('').every(function (c, j) { return s[j + possibilities[i].position] !== ''; })) {
for (j = 0; j < possibilities[i].word.length; j++) {
s[j + possibilities[i].position] = ''
}
}
fork(i + 1, s);
fork(i + 1, t);
}
var possibilities = array.reduce(function (r, a) {
var p = string.indexOf(a);
while (p !== -1) {
r.push({ word: a, position: p });
p = string.indexOf(a, p + 1);
}
return r;
}, []),
result = [];
console.log(possibilities);
fork(0, string.split(''));
console.log(result);
return result.some(function (a) { return !a; });
}
console.log(check("forthcarkeyboardingfor", ["for", "car", "key", "forth", "keyboard", "boarding"])); // true
console.log(check("forthxycarkeyboardingfor", ["for", "car", "key", "forth", "keyboard", "boarding"])); // false
.as-console-wrapper { max-height: 100% !important; top: 0; }
Version as above with early release.
function check(string, array) {
function fork(i, t) {
var s = t.slice(), j;
if (i === possibilities.length) {
return !t.join('');
}
if (possibilities[i].word.split('').every(function (c, j) { return s[j + possibilities[i].position] !== ''; })) {
for (j = 0; j < possibilities[i].word.length; j++) {
s[j + possibilities[i].position] = '';
}
}
return fork(i + 1, s) || fork(i + 1, t);
}
var possibilities = array.reduce(function (r, a) {
var p = string.indexOf(a);
while (p !== -1) {
r.push({ word: a, position: p });
p = string.indexOf(a, p + 1);
}
return r;
}, []);
return fork(0, string.split(''));
}
console.log(check("forthcarkeyboardingfor", ["for", "car", "key", "forth", "keyboard", "boarding"])); // true
console.log(check("forthxycarkeyboardingfor", ["for", "car", "key", "forth", "keyboard", "boarding"])); // false
source to share
Here is a more robust function that finds all the possible elements and methods that were used to create it. If the result length is zero, the source text cannot be made from the pool.
function decompose(orignal, pool) { // recurisve function to find combinations of text
var results = [];
for (var element of pool) { // for each element in pool
if (orignal == element) { // resursive base case, stop when orignal == element
results.push([element]); // * add solution
} else {
if (orignal.indexOf(element) == 0) { // if original text starts with element
var remaining = orignal.slice(element.length); // ready remaining text to be scanned
var subresults = decompose(remaining, pool); // recursive call: findCombinationsOf remaining
for (subresult of subresults) {
results.push([element].concat(subresult)); // * add solution
}
}
}
}
return results;
}
console.log(JSON.stringify(decompose("forthcarkeys", ["for","car","keys","forth"])));
console.log(JSON.stringify(decompose("forthcarkeys", ["for","car","keys","forth", "th"])));
console.log(JSON.stringify(decompose("nowaydude!", ["for","car","keys","forth", "th"])));
source to share
Here's my solution
More details:
- converts the given string
"forthcarxykeys"
to an array and assigns it to a variablechars
- iterate over a given array
["for","car","keys","forth"]
- for each iteration, check if the word exists in the array (i.e.
"for"
) - if it exists, get the index for each letter found and mark it as
true
in an arraychar
- return true if all values in
chars
are true, false if not.
JS:
// arr = ["for", "car", "keys", "forth"];
// str = "forthcarxykeys";
function check(arr, str) {
let chars = str.split('');
for (let i = 0; i < arr.length; i++) {
let word = arr[i];
let index = str.indexOf(word);
let wordExists = index !== -1;
if (wordExists) {
let endIndex = index + word.length;
for (index; index < endIndex; index++) {
chars[index] = true;
}
}
}
return chars.every(i => i === true);
}
source to share
Here's the updated code. String replace didn't work, so regex is used for that.var re = new RegExp(arr[i], 'g');
function check(str, arr) {
var flag = true;
for (var i = 0; i < arr.length; i++) {
if (str.indexOf(arr[i]) === -1) {
flag = false;
}
}
if (!flag) {
console.log("Some keys didn't matched.");
} else {
console.log("Nothing remains. All matched.");
}
}
var str = "forcarxy";
var arr = ["for", "car", "keys", "forth"];
check(str, arr);
var arr = ["abcd", "def", "abc"];
var str = "abcdef";
check(str, arr);
var arr = [ "abcd", "cdef" ];
var str = "abcdef";
check(str, arr);
var str = "aabc";
var arr = ["a", "bc"];
check(str, arr);
Code updated to address the commented case by @inetphantom
source to share