Encode Decode
Encode and Decode Strings
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
Use escape character ":" to node "spliter"
Use "+" as spliter
public String encode(List<String> strs) {
StringBuilder ans = new StringBuilder();
for(String s: strs){
for(char ch: s.toCharArray()){
if(ch == ':'){
ans.append(":");
}
ans.append(ch);
}
ans.append(":+");
}
return ans.toString();
}
public List<String> decode(String str) {
List<String> ans = new ArrayList<>();
char[] array = str.toCharArray();
StringBuilder tmp = new StringBuilder();
int i = 0;
while(i<array.length){
if(array[i] == ':'){
i++;
if(array[i] == '+'){
ans.add(tmp.toString());
tmp = new StringBuilder();
i++;
}else{
tmp.append(array[i]);
i++;
}
}else{
tmp.append(array[i++]);
}
}
return ans;
}
297. Serialize and Deserialize Binary Tree
Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'.
Pre-order traverse and use queue to store nodes
Use "#" as null
Use "," as spliter
def serialize(self, root):
s = ''
if root is None: s += '#' + ','
else:
s += str(root.val) + ','
s += self.serialize(root.left)
s += self.serialize(root.right)
return s
def deserialize(self, data):
q = data.split(',')
return self.dHelper(q)
def dHelper(self, q):
val = q.pop(0)
if val == '#': return None
else:
node = TreeNode(val)
node.left = self.dHelper(q)
node.right = self.dHelper(q)
return node
Last updated
Was this helpful?