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