Encode and Decode Strings
Encode and Decode Strings Problem
Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.
Please implement encode and decode
Output: ["prepinsta","course","are","best"]
Output: ["we","say",":","yes"]
Constraints:
- 0 <= strs.length < 100
- 0 <= strs[i].length < 200
- strs[i] contains only UTF-8 characters.
Encode and Decode Strings Solution
Recommendation –You should aim for a solution with O(m) time and O(1) space for each encode() and decode() call, where m is the sum of lengths of all the strings.
Hints for solving problems
Hint 1 :
A naive solution would be to use a non-ascii character as a delimiter. Can you think of a better way?
Hint 2:
Try to encode and decode the strings using a smart approach based on the lengths of each string. How can you differentiate between the lengths and any numbers that might be present in the strings?
Hint 3:
We can use an encoding approach where we start with a number representing the length of the string, followed by a separator character (let’s use # for simplicity), and then the string itself. To decode, we read the number until we reach a #, then use that number to read the specified number of characters as the string.
There are mainly 2 approach to solve this problem-
- Encoding and Decoding
- Encoding and Decoding(Optimal)
1. Encoding and Decoding Method
This method use a delimiter (like a special character or length-prefix) to encode strings, and split the encoded string using the same delimiter to decode. Simple but may face issues with delimiter conflicts.
- Time complexity: O(m) for encode() and decode().
- Space complexity: O(n) for encode() and decode().
where m is the sum of lengths of all the strings and n is the number of strings.
Code
class Solution {
public:
string encode(vector& strs) {
if (strs.empty()) return "";
vector sizes;
string res = "";
for (string& s : strs) {
sizes.push_back(s.size());
}
for (int sz : sizes) {
res += to_string(sz) + ',';
}
res += '#';
for (string& s : strs) {
res += s;
}
return res;
}
vector decode(string s) {
if (s.empty()) return {};
vector sizes;
vector res;
int i = 0;
while (s[i] != '#') {
string cur = "";
while (s[i] != ',') {
cur += s[i];
i++;
}
sizes.push_back(stoi(cur));
i++;
}
i++;
for (int sz : sizes) {
res.push_back(s.substr(i, sz));
i += sz;
}
return res;
}
};
public class Solution {
public String encode(List strs) {
if (strs.isEmpty()) return "";
StringBuilder res = new StringBuilder();
List sizes = new ArrayList<>();
for (String str : strs) {
sizes.add(str.length());
}
for (int size : sizes) {
res.append(size).append(',');
}
res.append('#');
for (String str : strs) {
res.append(str);
}
return res.toString();
}
public List decode(String str) {
if (str.length() == 0) {
return new ArrayList<>();
}
List res = new ArrayList<>();
List sizes = new ArrayList<>();
int i = 0;
while (str.charAt(i) != '#') {
StringBuilder cur = new StringBuilder();
while (str.charAt(i) != ',') {
cur.append(str.charAt(i));
i++;
}
sizes.add(Integer.parseInt(cur.toString()));
i++;
}
i++;
for (int sz : sizes) {
res.add(str.substring(i, i + sz));
i += sz;
}
return res;
}
}
class Solution:
def encode(self, strs: List[str]) -> str:
if not strs:
return ""
sizes, res = [], ""
for s in strs:
sizes.append(len(s))
for sz in sizes:
res += str(sz)
res += ','
res += '#'
for s in strs:
res += s
return res
def decode(self, s: str) -> List[str]:
if not s:
return []
sizes, res, i = [], [], 0
while s[i] != '#':
cur = ""
while s[i] != ',':
cur += s[i]
i += 1
sizes.append(int(cur))
i += 1
i += 1
for sz in sizes:
res.append(s[i:i + sz])
i += sz
return res
class Solution {
/**
* @param {string[]} strs
* @returns {string}
*/
encode(strs) {
if (strs.length === 0) return "";
let sizes = [], res = "";
for (let s of strs) {
sizes.push(s.length);
}
for (let sz of sizes) {
res += sz + ',';
}
res += '#';
for (let s of strs) {
res += s;
}
return res;
}
/**
* @param {string} str
* @returns {string[]}
*/
decode(str) {
if (str.length === 0) return [];
let sizes = [], res = [], i = 0;
while (str[i] !== '#') {
let cur = "";
while (str[i] !== ',') {
cur += str[i];
i++;
}
sizes.push(parseInt(cur));
i++;
}
i++;
for (let sz of sizes) {
res.push(str.substr(i, sz));
i += sz;
}
return res;
}
}
2. Encoding and Decoding Method(Optimal)
This method store the length of each string before the string itself during encoding. During decoding, read the length first to extract the exact substring, avoiding delimiter-related issues.
- Time complexity: O(m) for encode() and decode().
- Space complexity: O(1) for encode() and decode().
where m is the sum of lengths of all the strings and n is the number of strings.
Code
class Solution {
public:
string encode(vector& strs) {
string res;
for (const string& s : strs) {
res += to_string(s.size()) + "#" + s;
}
return res;
}
vector decode(string s) {
vector res;
int i = 0;
while (i < s.size()) {
int j = i;
while (s[j] != '#') {
j++;
}
int length = stoi(s.substr(i, j - i));
i = j + 1;
j = i + length;
res.push_back(s.substr(i, length));
i = j;
}
return res;
}
};
public class Solution {
public String encode(List strs) {
StringBuilder res = new StringBuilder();
for (String s : strs) {
res.append(s.length()).append('#').append(s);
}
return res.toString();
}
public List decode(String str) {
List res = new ArrayList<>();
int i = 0;
while (i < str.length()) {
int j = i;
while (str.charAt(j) != '#') {
j++;
}
int length = Integer.parseInt(str.substring(i, j));
i = j + 1;
j = i + length;
res.add(str.substring(i, j));
i = j;
}
return res;
}
}
class Solution:
def encode(self, strs: List[str]) -> str:
res = ""
for s in strs:
res += str(len(s)) + "#" + s
return res
def decode(self, s: str) -> List[str]:
res = []
i = 0
while i < len(s):
j = i
while s[j] != '#':
j += 1
length = int(s[i:j])
i = j + 1
j = i + length
res.append(s[i:j])
i = j
return res
class Solution {
/**
* @param {string[]} strs
* @returns {string}
*/
encode(strs) {
let res = "";
for (let s of strs) {
res += s.length + "#" + s;
}
return res;
}
/**
* @param {string} str
* @returns {string[]}
*/
decode(str) {
let res = [];
let i = 0;
while (i < str.length) {
let j = i;
while (str[j] !== '#') {
j++;
}
let length = parseInt(str.substring(i, j));
i = j + 1;
j = i + length;
res.push(str.substring(i, j));
i = j;
}
return res;
}
}
