Array searching and slicing-CodePudding

Given the string nums that contains only digits and the array of numbers predefinedNumbers, I have to construct a new string, based on nums but where each number between colons has to be a valid number from predefinedNumbers and return all possibilities.

Example input:

nums = "143163421154143"
predefinedNumbers = ["21154", "143", "21154143", "1634", "163421154"]

Desired output:

[ ":143:1634:21154:143:", ":143:163421154:143:", ":143:1634:21154143:" ]

So far I tried this code but it's not the result I need and I'm stuck trying to understand how to go over it recursively:

let nums = "143163421154143";
predefinedNumbers = ["21154", "143", "21154143", "1634", "163421154"];


let newArray=[];
function makeNumSentences (nums, predefinedNumbers) {
    predefinedNumbers.map(item => {
        if (nums.includes(item)) {
            newArray.push(item)
        }
    })
    
    console.log(newArray.join(':'));
        };
        
        
makeNumSentences("143163421154143",["21154", "143", "21154143", "1634", "163421154"])

Any hint is very much appreciated.

CodePudding user response：

Please note that the loops will never end in case the nums is not composed of predefinedNumbers only.

const nums = "143163421154143";
const predefinedNumbers = ["21154", "143", "21154143", "1634", "163421154"];
const result = [];

function makeNumSentences(nums) {
  check([], nums);
  console.log(result);
};

function check(array, nums) {
  predefinedNumbers.forEach(e => {
    if (nums.startsWith(e)) {
      const newArray = array.concat(e);
      const newNums = nums.slice(e.length);
      if (newNums) { check(newArray, newNums); }
      else { result.push(newArray.join(':')); }
    }
  });
}
        
        
makeNumSentences(nums);

CodePudding user response：

First, please read How do I ask and answer homework questions?.

Since there is already an accepted answer, though, I will just show an alternate technique. The fact that the elements are digits is meaningless. This same technique will work for any strings. (There are mathematical techniques to find the right value, but they would quickly overflow normal numbers, and since the output needs to be a string in any case, there seems to be no need to pursue them.)

Thinking about this recursively, we can break this into two pieces. Which of my predefined values appear in the start of my target string? And for each one of those, how do I perform the same operation on the remainder of the string? A recursion needs a base case, and we can say that if the target string is empty, then we can return a single empty string.

We can implement it like this:

const make = (target, sources) =>
  target .length == 0
    ? [[]]
    : sources .filter (s => target .startsWith (s)) 
              .flatMap (s => make (target .slice (s .length), sources) .map (r => [s, ...r]))

const makeNumSentences = (target, parts) => 
  make (target, parts) .map (r => `:${r.join(':')}:`)


const nums = "143163421154143"
const predefinedNumbers = ["21154", "143", "21154143", "1634", "163421154"]

console .log (makeNumSentences (nums, predefinedNumbers))

Notice the breakdown into a main recursive function, which returns an array of arrays of elements from our sources ([["143", "1634", "21154", "143"], ["143", "1634", "21154143"], ["143", "163421154", "143"]]) and a wrapper which combines them into the output format. ([":143:1634:21154:143:", ":143:1634:21154143:", ":143:163421154:143:"]). This is to my mind the proper breakdown of the work. Arrays are nice to work with and we can do much more with them. But this is not the only way to go. We can alter this to return the strings directly:

const make = (target, sources) =>
  target .length == 0
    ? ['']
    : sources 
       .filter (s => target .startsWith (s)) 
       .flatMap (s => make (target .slice (s .length), sources) .map (r => `:${s}${r}`    (r ? '' : ':')))

const nums = "143163421154143"
const predefinedNumbers = ["21154", "143", "21154143", "1634", "163421154"]

console .log (make (nums, predefinedNumbers))

Note that there is some additional complexity here in building the strings. This is because of the trailing ":". We want to add that only on the first step when the existing string is empty. (We always add the leading one.)