Discussion on: Daily Challenge #151 - Reverse Parentheses

View post

Javascript

My solution has both time and space complexity of O(n) I believe. The first pass is to create a tree, the second pass is to convert the tree to a string recursively. In fact, reconstructing a string uses multiple passes but their number is constant (reverse, map, join), and it's possible to rewrite the toStr function to use a single pass but the code won't be as concise. Reversion is only done at odd levels as at an even level it is reverted again back to original state.

function reverseInParens(str) {
  const toStr = (node, lvl = 0) => {
    const result = (lvl % 2 < 1 ? node.items : node.items.reverse())
      .map(i => (i.items ? toStr(i, lvl + 1) : i))
      .join("");
    return lvl > 0 ? `(${result})` : result;
  };
  let current = { items: [] };
  for (let i = 0; i < str.length; i++) {
    if (str[i] === "(") {
      let nested = { parent: current, items: [] };
      current.items.push(nested);
      current = nested;
    } else if (str[i] === ")") {
      current = current.parent;
    } else {
      current.items.push(str[i]);
    }
  }
  return toStr(current);
}