leetcode271- Encode and Decode Strings- medium

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.

本题难度不在对字符加密，而在怎么把各个字符串分开。本来字符已经占用了任意可用的256种了，所以你不能简单地选一个分隔符然后用split。

最后用的方法是，加密时用 长度+‘#‘+真正字符串的形式去加（实践真的可行，哪怕实际有分隔符的字符，因为你说明了长度了你把它取出来后下一个使用indexOf就不会影响了。而且第一个分隔符肯定来自于真正的分隔符，所以递推下去就都不会有问题了）。

解密时每次 1.indexOf(‘#‘, idx)，从指针所指的位置开始找第一个分隔符。2.上个指针到当前分割点语意理解后就是字符串长度。3.后面取出字符串即可。

实现：

public class Codec { ???// Encodes a list of strings to a single string. ???public String encode(List<String> strs) { ???????StringBuilder sb = new StringBuilder(); ???????for (int i = 0; i < strs.size(); i++) { ???????????sb.append(strs.get(i).length()); ???????????sb.append(‘#‘); ???????????sb.append(strs.get(i)); ???????} ???????return sb.toString(); ???} ???// Decodes a single string to a list of strings. ???public List<String> decode(String s) { ???????List<String> result = new ArrayList<>(); ???????int idx = 0; ???????while (idx < s.length()) { ???????????int cut = s.indexOf(‘#‘, idx); ???????????int length = Integer.parseInt(s.substring(idx, cut)); ???????????result.add(s.substring(cut + 1, cut + 1 + length)); ???????????idx = cut + length + 1; ???????} ???????return result; ???}}// Your Codec object will be instantiated and called as such:// Codec codec = new Codec();// codec.decode(codec.encode(strs));

leetcode271- Encode and Decode Strings- medium

原文地址：http://www.cnblogs.com/jasminemzy/p/7965947.html