HOW TO CHECK IF DOM ELEMENTS ARE CORRECTLY NESTED

Question

i need help with this coding challenge.

Have the function HTMLElements(str) read the str parameter being passed which will be a string of HTML DOM elements and plain text. The elements that will be used are: b, i, em, div, p. For example: if str is "<div><b><p>hello world</p></b></div>" then this string of DOM elements is nested correctly so your program should return the string true.

If a string is not nested correctly, return the first element encountered where, if changed into a different element, would result in a properly formatted string. If the string is not formatted properly, then it will only be one element that needs to be changed. For example: if str is "<div><i>hello</i>world</b>" then your program should return the string div because if the first element were changed into a <b>, the string would be properly formatted.

example:

Input: "<div><div><b><b/></div><p/>"
output: <div>

Input: "<div>abc</div><p><em><i>test test test</b></em></p>"
output: i

Here is how far I've gotten:

function HTMLElements(str) { 

 let openingTag = str.match(/<\w+>/g)
 let closingTag = str.match(/(<\/\w+>)/g)
 let strObj = {
  '<div>': '</div>',
  '<p>': '</p>',
  '<i>': '</i>',
  '<p>': '</p>',
  '<em>': '</em>',  
  '<b>': '</b>',
  }

  let unclosedElem = []

  for(let i=0; i<openingTag.length; i++){
     console.log(closingTag)
    if(closingTag.indexOf(strObj[openingTag[i]]) ===-1){
      unclosedElem.push(closingTag.splice(closingTag.indexOf(strObj[openingTag[i]]),1))
    }
  }
  console.log(unclosedElem)
  if(unclosedElem.length === 0) return true;
  return unclosedElem[0]
} 

// keep this function call here 
HTMLElements("<div><div><b><b/></div></p>")

now i understand this is far from solving the challenge but i guess it's a start for me. I will eventually solve this but your inputs are appreciated

Answer 1

There are a couple of issues.

First, you are doing closingTag.indexOf(...) === -1. If it's equal to -1, it means that this closing tag was not found at all. But the requirement is to "detect a problem" even if the closing tag is here, but in the wrong order (not nested correctly).

So, a first fix you could do is:

closingTag.indexOf(...) !== closingTag.length - i

This would count backward from the end of the closing tags array. Because the first opening tag corresponds to the last closing tag.

But then, we have a problem. indexOf will return the first occurrence of a tag. But what if we have multiple div tags nested inside of each other? It would not know which one you're referring to.

My suggestion, instead of using indexOf, would be to go from left to right in the opening tags array, while going from right to left in the closing tags array. An easy way to do it is to .reverse() the second array so that you can go in the same direction with both:

function HTMLElements(str) {
  let openingTags = str.match(/<\w+>/g)
  let closingTags = str.match(/(<\/\w+>)/g).reverse();
  let strObj = {
    '<div>': '</div>',
    '<p>': '</p>',
    '<i>': '</i>',
    '<p>': '</p>',
    '<em>': '</em>',
    '<b>': '</b>',
  };
  
  // There might not be the same number of opening and closing tags
  const max = Math.max(openingTags.length, closingTags.length);
  
  for (let i = 0; i < max; i++) {
    if (strObj[openingTags[i]] !== closingTags[i]) {
      return (openingTags[i] || closingTags[i]).replace(/<|>/g, '');
    }
  }

  return true;
}

function demo(str) {
  const res = HTMLElements(str);
  console.log(str, '\t--> ', res);
}

demo("<div><div><b><b/></div></p>"); // "div" (closing a `div` with a `p`)
demo("<p><div><b><b/></div></p>");   // "b" (because `<b/>` is invalid)
demo("<p><div></p></div>");          // "p" (wrong order)
demo("<p><div><b></b>");             // "p" (not closed at all)
demo("<p><div></b></div></p>");      // "/b" (not opened)
demo("<p><div><b></b></div></p>");   // true

Answer 2

Further work on blex's solution to account for case strings such as <div>abc</div><p><em><i>test test test</b></em></p> where the div tag was opened and closed right away and not having any other tags nested in it.

function HTMLElements(str) {
  const openingTags = str.match(/<\w+>/g)
  const closingTags = str.match(/(<\/\w+>)/g);
  
  const strObj = {
    '<div>': '</div>',
    '<p>': '</p>',
    '<i>': '</i>',
    '<p>': '</p>',
    '<em>': '</em>',
    '<b>': '</b>',
  };
  
  // there might not be the same number of opening and closing tags
  const max = Math.max(openingTags.length, closingTags.length);
  
  for (let i = 0; i < max; i++) {
    if (strObj[openingTags[i]] !== closingTags[closingTags.length - 1] && strObj[openingTags[i]] !== closingTags[0]) {
      return (openingTags[i]).replace(/<|>/g, '');
    }
      closingTags.splice(closingTags.indexOf(strObj[openingTags[i]]),1);
  }

  return "true";
}

console.log(HTMLElements("<div><b><p>hello world</p></b></div>"));
console.log(HTMLElements("<div><i>hello</i>world</b>"));
console.log(HTMLElements("<div><div><b><b/></div><p/>"));
console.log(HTMLElements("<div>abc</div><p><em><i>test test test</b></em></p>"));
console.log(HTMLElements("<div><p></p><em><div></div></em></div>"));

But when I think more deeply about the problem and take into account "If a string is not nested correctly, return the first element encountered where, if changed into a different element, would result in a properly formatted string. If the string is not formatted properly, then it will only be one element that needs to be changed", this condition sure helps, knowing that it can only be one element not nested correctly👌🏾 That said, I think a better solution and approach would be:

function HTMLElements(str) {
  const openingTags = str.match(/<\w+>/g)
  const closingTags = str.match(/(<\/\w+>)/g);
  
  const strObj = {
    '<div>': '</div>',
    '<p>': '</p>',
    '<i>': '</i>',
    '<p>': '</p>',
    '<em>': '</em>',
    '<b>': '</b>',
  };

  for(let i = 0; i < openingTags.length; i++) {
    const openingTag = openingTags[i];
    const closingTag = strObj[openingTag];
    if (closingTag) {
      const closingTagIndex = closingTags.indexOf(closingTag);
      if (closingTagIndex > -1) {
        closingTags.splice(closingTagIndex, 1);
      }
      else return openingTags[i].replace(/<|>/g, '');
    }
  }
  return "true";
}

console.log(HTMLElements("<div><b><p>hello world</p></b></div>"));
console.log(HTMLElements("<div><i>hello</i>world</b>"));
console.log(HTMLElements("<div><div><b><b/></div><p/>"));
console.log(HTMLElements("<div>abc</div><p><em><i>test test test</b></em></p>"));
console.log(HTMLElements("<div><p></p><em><div></div></em></div>"));

Another approach would be to make a frequency count of the tags using dictionaries and do a comparison for the ones that don't add up:

function HTMLElements(str) {
  const openingTags = str.match(/<\w+>/g)
  const closingTags = str.match(/(<\/\w+>)/g);
  
  const strObj = {
    '<div>': '</div>',
    '<p>': '</p>',
    '<i>': '</i>',
    '<p>': '</p>',
    '<em>': '</em>',
    '<b>': '</b>',
  };
  
  const expectedClosingTagsDict = {};
  openingTags.forEach(tag => {
    const validClosingTag = strObj[tag];
    if(validClosingTag) {
      expectedClosingTagsDict[validClosingTag] ? expectedClosingTagsDict[validClosingTag]++ : expectedClosingTagsDict[validClosingTag] = 1;
    }
  });

  const actualClosingTagsDict = {};
  closingTags.forEach(tag => {
    actualClosingTagsDict[tag] ? actualClosingTagsDict[tag]++ : actualClosingTagsDict[tag] = 1;
  });

  for (let tag in expectedClosingTagsDict){
    if (expectedClosingTagsDict[tag]  !== actualClosingTagsDict[tag]) return tag.replace(/<|\/|>/g, '');
  }
  return "true";
}

console.log(HTMLElements("<div><b><p>hello world</p></b></div>"));
console.log(HTMLElements("<div><i>hello</i>world</b>"));
console.log(HTMLElements("<div><div><b><b/></div><p/>"));
console.log(HTMLElements("<div>abc</div><p><em><i>test test test</b></em></p>"));
console.log(HTMLElements("<div><p></p><em><div></div></em></div>"));

Not sure which is the fastest but I'd definitely pick my second or third solution over the first when thinking of performance, space & time complexity, and readability. I think I'd finally pick the third solution over the second one as the third would run in O(n) whereas the second is not guaranteed to run in O(n) but looks more like O(n * m), more akin to quadratic time due to the nested splice in the for-loop. A whole lot more to discuss and factor in here but in the end, you can just do timed tests and pick one over the other really 🤷🏾‍♂️