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

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.

CodePudding user response：

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

CodePudding user response：

Assuming your data is always properly sorted, like in the example, we can do this in linear time using a stack. The basic algorithm would be like this:

init the stack with a dummy item
take each data item
compare data item with the top of the stack (TOS)
if the item > TOS (like 1.1 > 1), push it to the stack and continue
otherwise, output everything on the stack concatenated
while item <= TOS, keep popping items off the stack
in the end, output everything that's left on the stack