Print all paths to leafs of a tree-like list array and concatenate corresponding values in the path

Issue

I have an array consisting of keys and values where keys are a tree like numbered list.
This is the input array:

inputArr =     [
                ["1", "I can "], 
                ["1.1", "speak "],
                ["1.1.1", "English."], 
                ["1.1.2", "Chinese."], 
                ["1.2", "eat noodles."],
                ["1.3", "play football."],
                ["2", "I "],
                ["2.1", "drink."],
                ["2.2", "sleep."],
                ["3", "I am the man."],
                ["4", "Hire me."]
               ]

Expected output:

outputArr =    [
                ["1.1.1", "I can speak English."],
                ["1.1.2", "I can speak Chinese."],
                ["1.2", "I can eat noodles."],
                ["1.3", "I can play football."],
                ["2.1", "I drink."],
                ["2.2", "I sleep."],
                ["3", "I am the man."],
                ["4", "Hire me."]
               ]

Let me explain the first output:
The first leaf in the inputArray is "1.1.1". It’s path is: "1"->"1.1"->"1.1.1". When the
values in the path are concatenated: "I can " + "speak " + "English.".

I have studied all the relevant stackoverflow questions. I have got no clues to my problem.

I am thinking of an algorithm like this:

iterating from bottom of the array:
if the key length is 1, it is a root parent item.
if the key above has length >1, it is a leaf item. Now, get path by splitting the key, and concatenate the corresponding values.

Can you suggest how to produce this output?
Any algorithm, a piece of code, any hint about the problem will be much appreciated.

Solution

This can be definitely improved, but it works.

function getSentences(arr) {

  let outputArr = [], s = [], curr, next;

  for (let i=0; i < arr.length-1; i++) {
    curr = arr[i];
    next = arr[i+1];

    if (curr[0].length == 1) {
      s.push(curr[1]);
      if (curr[0].length == next[0].length) outputArr.push([curr[0], s.join('')]);
    }

    else if (curr[0].length < next[0].length) {
      s.push(curr[1]);
    }

    else if (curr[0].length >= next[0].length) {
      outputArr.push([curr[0], s.join('') + curr[1]]);
      if (curr[0].length > next[0].length) {
        s.pop();
      }
    }
  }

  for (i=0; s.length == next[0].length; i++) {
    s.pop()
  }
  s.push(next[1])
  outputArr.push([next[0], s.join('')])

  console.log(outputArr);
  return outputArr

}

This function assumes something like "1.12.2" shouldn’t exist and that the array is sorted like in the example.
If you want it to work with the hypothetical "1.12.2", replace .length in the comparisons with path.replace(/[^.]/g, "").length

Answered By – Bit

This Answer collected from stackoverflow, is licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0

Leave a Reply

(*) Required, Your email will not be published