# 271 Encode and Decode Strings

## 271.[ Encode and Decode Strings](https://leetcode.com/problems/encode-and-decode-strings/description/)

## 1. Question

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.

Machine 1 (sender) has the function:

```
string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}
```

Machine 2 (receiver) has the function:

```
vector<string> decode(string s) {
  //... your code
  return strs;
}
```

So Machine 1 does:

```
string encoded_string = encode(strs);
```

and Machine 2 does:

```
vector<string> strs2 = decode(encoded_string);
```

`strs2`in Machine 2 should be the same as`strs`in Machine 1.

Implement the`encode`and`decode`methods.

**Note:**

* The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
* Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
*   Do not rely on any library method such as

    `eval`

    or serialize methods. You should implement your own encode/decode algorithm.&#x20;

## 2. Implementation

```
public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder code = new StringBuilder();
        for (String str : strs) {
            code.append(str.length()).append("/").append(str);
        }
        return code.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> strs = new ArrayList();
        int index = 0;
        while (index < s.length()) {
            int slashIndex = s.indexOf("/", index);
            int size = Integer.parseInt(s.substring(index, slashIndex));
            strs.add(s.substring(slashIndex + 1, slashIndex + size + 1));
            index = slashIndex + size + 1;
        }
        return strs;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));
```

## 3. Time & Space Complexity

时间复杂度: encode:O(n), decode: O(n^2), n为decode string的长度，substring()需要O(n)的时间, 空间复杂度O(n)
