Encoding and Decoding a String - A Simple Algorithm Using Javascript #Leetcode 659

Leetcode Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

In this blog post, we will explore a simple algorithm to encode and decode a given string. The algorithm involves converting a list of words into a special format and then reversing the process to retrieve the original words. Let's dive into the details!

Encoding:

To encode the string, we begin with an empty string. We iterate through each word in the given list and perform the following steps:

Take an empty string.
Loop through each word and calculate its length.
Convert the length to a string representation.
Concatenate the length, a dollar sign ($), and the word to the empty string.
Repeat this process for all words in the list.
Finally, return the encoded string.

The implementation of the encoding function is as follows:

const encode = (words) => {
  let res = "";
  for (let word of words) {
    let len = word.length;
    res += Number(len) + "$" + word;
  }
  return res;
}

Decoding:

To decode the encoded string and retrieve the original words, we utilize two pointers, i and j, respectively.

Initialize i to 0, which represents the starting index of the string.
Run a while loop until i reaches the last index of the string.
Inside the while loop, initialize j as a pointer starting from index i.
Run another while loop until j reaches the dollar sign ($) character.
Extract the length of the word by converting the substring from index i to j back to a number using the slice method.
Slice the encoded string from index j + 1 to j + 1 + length to obtain the word.
Add the word to an array.
Update the i pointer based on the current position of j and the length of the word.
Repeat steps 3-8 until the entire string is decoded.
Finally, return the array of decoded words.

The implementation of the decoding function is as follows:

const decode = (word) => {
  let res = [],
    i = 0;
  while (i < word.length) {
    let j = i;
    while (word[j] !== "$") {
      j++;
    }
    let len = Number(word.slice(i, j));
    let w = word.slice(j + 1, j + 1 + len);
    res.push(w);
    i = j + len + 1;
  }
  return res;
}

Now you can test both the functions using the javascript console like below:

let words = ["This", "is", "a", "secret"];
let word = "4$This2$is1$a6$secret";
console.log(encode(words));
console.log(decode(word));

The time complexity of this algorithm is O(n), where n represents the length of the encoded string.

In conclusion, we have explored a simple algorithm to encode and decode a string using JavaScript. This approach can be useful in various scenarios where string transformations are required. Feel free to use this algorithm in your projects or explore further modifications based on your specific needs.

Thank you for reading, and happy coding!

Encoding and Decoding a String - A Simple Algorithm Using Javascript #Leetcode 659

Table of contents

No headings in the article.