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.
Please implement encode and decode.
Input: ["cs","code","love","you"]
Output: ["cs","code","love","you"]
Explanation: One possible encode method is: "cs:;code:;love:;you".
Input: ["we", "say", ":", "yes"]
Output: ["we", "say", ":", "yes"]
Explanation: One possible encode method is: "we:;say:;:::;yes"
Contents
- Solution 1 - Prepend string length and a separator symbol when encoding and decode them using the same
In this approach, When encoding we are going to prepend each string from input array with its length and a symbol character for example #.
Then, when decoding we know that the number before first # symbol is the length of the first string, so decode the first string and continue
the same process for remaining strings.
Implementation details for encode:
-
We will loop through each string from input array and prepend the string with its length followed by a symbol character as a way to identify the
starting string length and the actual string (you can choose any symbol character as you wish).
For example if the input strings array is strs = ["cs", "code", "love", "you"] then the encoded string will become 2#cs4#code4#love3#you
static String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for(String str: strs) {
sb.append(str.length()).append("#").append(str);
}
return sb.toString();
}
Implementation details for decode:
-
First, we will create a variable currentIndex to keep track of current position of encoded string.
-
Next, find the starting string length by taking the substring from currentIndex to the first position of '#' starting from currentIndex.
For example, if the encoded string is 2#cs4#code4#love3#you:
-
Initially currentIndex will be 0
and the next # symbol starting from index 0 is at index 1, so the substring between currentIndex and
the index we found immediate # symbol is 2.
Then we take the substring after # symbol with length 2, that will be "cs", now we will move currentIndex
to next index after we got the first string from encoded string which will be 5.
-
We now repeat this process for above step until we reach the end.
static List<String> decode(String str) {
// write your code here
List<String> list = new ArrayList<>();
int currentIndex = 0;
while(currentIndex < str.length()) {
int separatorPos = str.indexOf("#", currentIndex);
String actualStrLength = str.substring(currentIndex, separatorPos);
int length = Integer.parseInt(actualStrLength);
String actualStr = str.substring(separatorPos+1, separatorPos+length+1);
currentIndex = separatorPos+actualStr.length()+1;
list.add(actualStr);
}
return list;
}
Above approach will work even if the strings contains the symbol that we are using in encode process, because we start with the length of
first string, that can be found before the first occurrence of # symbol and we get the first string, and we repeat this process,
so in each iteration, we can simply look for first occurrence of # symbol from the current position we are at to get the next string length.
Implementation:
import java.util.ArrayList;
import java.util.List;
public class EncodeAndDecodeStrings {
static String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for(String str: strs) {
sb.append(str.length()).append("#").append(str);
}
return sb.toString();
}
static List<String> decode(String str) {
// write your code here
List<String> list = new ArrayList<>();
int currentIndex = 0;
while(currentIndex < str.length()) {
int separatorPos = str.indexOf("#", currentIndex);
String actualStrLength = str.substring(currentIndex, separatorPos);
int length = Integer.parseInt(actualStrLength);
String actualStr = str.substring(separatorPos+1, separatorPos+length+1);
currentIndex = separatorPos+actualStr.length()+1;
list.add(actualStr);
}
return list;
}
public static void main(String[] args) {
List<String> s1 = List.of("cs","code","love","you");
String encodedS1 = encode(s1);
System.out.println("Encoded string of "+s1+" is : "+encodedS1);
System.out.println("Decoded string of "+s1+" is : "+decode(encodedS1));
List<String> s2 = List.of("#cs#","#code#","#love#","#you#");
String encodedS2 = encode(s2);
System.out.println("Encoded string of "+s2+" is : "+encodedS2);
System.out.println("Decoded string of "+s2+" is : "+decode(encodedS2));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n is the input strings array length.
Space complexity: O(1) since we are not using any extra space in encode or decode process.
Above implementations source code can be found at
GitHub link for Java code