Given a string and an array representing the HTML encoding of the string from and to with the given tag. Return the HTML encoded string.
Example
Input: const str = 'Hello, world'; const styleArr = [[0, 2, 'i'], [4, 9, 'b'], [7, 10, 'u']]; Output: '<i>Hel</i>l<b>o, w<u>orl</u></b><u>d</u>'
Note – <u> tag gets placed before the <b> tag and after it as the insertion index overlaps it.
It is one of the most common feature that is implemented in the WYSWIG editors, where you write normal text and apply styles to it and it will converted to HTML encoding at the end.
There are two ways to solve this question.
First one is extremely simple as most of the work is done by a inbuilt method.
In the second one, we write the complete logic for encoding.
Let us first see the second method as most of the times in the interview you will be asked to implement this way only.
Custom algorithm for HTML encoding of the string
The styles can be overlapping thus one tag can overlap the other and in such scenarios we have to close the overlapping tags and re-open it again.
Input: const str = "Hello, World"; const style = [0, 2, 'i'] , [1, 3, 'b']; Output: <i>H<b>el</b></i><b>l</b>o, World // b is starting from 1 and ending at 3, i is inbetween b.
As you can see in the above example b is overlapping thus it is closed at 2nd character of the string and re-opnend at 3.
We can solve implement this with the help of a priority queue and a stack.
- Aggregate the styles on the starting index in the order of priority of the range difference between them. (endIndex – startIndex), this way the longest tag is created first.
- Now using a stack, track the opening and closing of tags.
- If the current styles ending indexes is greater than the previous one, then create a new tag as it is overlapping and push this new entry back to the stack and in next iteration create this tag.
- At the end return the string of the top most stack entry.
Priority queue
We are not going to use the complete implementation of Priorty Queue rather a helper function that adds a new item in the array and sorts it in the ascending or descending order depending upon the order.
// helper function works as Priority queue
// to add tags and sort them in descending order
// based on the difference between the start and end
function addAndSort(track, index, data) {
if (!track[index]) track[index] = [];
track[index] = [...track[index], data];
track[index].sort((a, b) => a.getRange() > b.getRange());
};
Stack
A simple implementation of the Stack data structure with the required methods.
function Stack() {
let items = [];
let top = 0;
//Push an item in the Stack
this.push = function (element) {
items[top++] = element;
};
//Pop an item from the Stack
this.pop = function () {
return items[--top];
};
//Peek top item from the Stack
this.peek = function () {
return items[top - 1];
};
};
Tag method
A helper function to creat a new tag for each entry of styles and its corresponding, also helps to get the range for easier processing in the priority queue. We push this in the priority queue and sort it.
// helper function to form a tag
// and trace the string
function Tag(start, end, tag) {
this.start = start;
this.end = end;
this.tag = tag;
this.text = "";
this.getRange = () => {
return this.end - this.start;
};
};
Encoder method
In this method we perform all the encoding step by step.
- Create an empty array
traceof the size of the input string. - Iterate the styles and form a new tag for each entry.
- On the start index of the styles aggregate the common tags in the priority queue based on the difference of their range in descending order.
- Add these priority queue in the at the start indexes of the styles in the
trace. - Create a new stack and add an initial Tag with maximum range i.e
Tag(start = 0, end = Number.MAX_VALUE, tag = ""). - Iterate till input string length, get the tags from the
traceat each index, itearte the prioritized tags if they are present. - Create the opening HTML tag for each tag in the queue and push it in the stack. Check if the current end Index of the tag is greater than the previous one in the stack, then create a new tag and push it in the priority queue.
- At the end close all the HTML tags at the given index in the loop.
function parse(str, markups) {
// create an empty array for all the indexes of the string
const track = new Array(str.length).fill(null);
// add the tag at the starting point
// of each text mentined in the markups
for (let markup of markups) {
const [start, end, tag] = markup;
addAndSort(track, start, new Tag(start, end, tag));
}
// create a new stack
const html = new Stack();
// initilize with a new Tag that has max range and empty string
html.push(new Tag(0, Number.MAX_VALUE, ""));
// iterate each character of the string
for (let i = 0; i < str.length; i++) {
// check for opening tags and add them
while (track[i] && track[i].length > 0) {
const cur = track[i].shift();
cur.text = `<${cur.tag}>`;
// for example in [0, 2, 'i'] , [1, 3, 'b']
// b is starting from 1 and ending at 3, i is inbetween b.
// <i> <b> </b> </i> <b> </b>
// if the end of the nested tag is larger than the parent, split the tag
// and insert the remaining split to the bucket after its parent
if (cur.end > html.peek().end) {
const split = new Tag(html.peek().end + 1, cur.end, cur.tag);
cur.end = html.peek().end;
addAndSort(track, html.peek().end + 1, split);
}
// push the new tag
html.push(cur);
}
// add the current character to the currently topmost tag
html.peek().text += str[i];
// heck for closing tags and close them.
while (html.peek().end === i) {
html.peek().text += `</${html.peek().tag}>`;
const temp = html.pop().text;
html.peek().text += temp;
}
}
// return the topmost
return html.pop().text;
};
Input:
const encoded = parse('Hello, World',
[[0, 2, "i"],
[7, 10, "u"],
[4, 9, "b"],
[2, 7, "i"],
[7, 9, "u"]]);
console.log(encoded);
Output:
"<i>He<i>l</i></i><i>l<b>o, <u><u>W</u></u></b></i><b><u><u>or</u></u></b><u>l</u>d"
"Hello, World"
Using DOMParser()
DOMParser() parses the HTML source code from the string and the good thing is appropriately places the opening and closing tags if it is missing.
Thus all we have to do is traverse the styles and add tags at the mentioned opening and closing positions in the input string.
Then pass this string to the DOMParser() and it will generate the HTML from the string.
function parse(string, markups) {
// place the opening and closing tags at the appropriate indexes
const fragments = markups.reduce((chars, [start, end, tag]) => {
chars[start] = `<${tag}>` + chars[start];
chars[end] += `</${tag}>`;
return chars;
}, [...string]);
// pass this string to DOMParser()
// to convert it to HTML
return new DOMParser()
.parseFromString(fragments.join(''), 'text/html')
.body.innerHTML;
}
const encoded = parse('Hello, World',
[[0, 2, "i"],
[7, 10, "u"],
[4, 9, "b"],
[2, 7, "i"],
[7, 9, "u"]]);
console.log(encoded);
Output:
"<i>He<i>l</i>l<b>o, <u><u>W</u></u></b></i><b><u><u>or</u></u></b><u>l</u>d"
"Hello, World"