Skip to content

How to properly call a recursive function inside a for loop?

I’m trying to implement a method that takes as a parameter: target string and an array with string values in it. The goal is to check if it is possible to construct with array’s value, the given target string.The words in array can be used as many times as we want. Example:

console.log(canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"])); // suppose to return true

As we can see, by concatenating "abc" and "def" we get the target string of "abcdef" Here is my function implementation:

const canConstruct = function (target, wordBank) {
  if (target === "") return true;
  console.log(target);
  for (let word of wordBank) {
    if (target.startsWith(word)) {
      return canConstruct(target.replace(word, ""), wordBank);
    }
  }

  return false;
};  

Line 2 is a base case for this recursion function, then by iterating through the array check if it starts with the array element, if true then remove that specific subarray and call again the function with the new target string and old array, if false keep iterating through entire function till it hits the base case. So again using the previous example:

console.log(canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]));  // return false

I’m getting false, and by debugging I can see that it didn’t iterate the whole array from since first recursive call. I get the following output:

abcdef
cdef
ef
false

Answer

You are breaking for loop even if you return false and skiping all other combinations that way. So you are founding only one path, in your case

ab
cd

const canConstruct = function (target, wordBank) {
    if (target === "")
        return true;
    for (let word of wordBank) {
        if (target.startsWith(word)) {
            if (canConstruct(target.replace(word, ""), wordBank))//break it only if true
                return true;
        }
    }

    return false;
};
console.log("abcdef", canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]));

console.log("abc1def", canConstruct("abc1def", ["ab", "abc", "cd", "def", "abcd"]));