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.
Solution:...+ s.length() + '/' + s + ...;
思路:將strs放在一個(gè)string里要能夠提取出來(lái),主要是要知道各個(gè)str的長(zhǎng)度县匠。那么就可以將str的長(zhǎng)度len放在str前面,但是有可能str的開頭就是數(shù)字丛版,所以加一個(gè)separator '/' 這樣一來(lái),收到一串string偏序,找到第一個(gè)'/'页畦,前面是len,在第一個(gè)'/'后提取len個(gè)字符研儒,循環(huán)下去寇漫。
(Note: 所以這里的上separator只要不是char(數(shù)字)別的都可以)
Time Complexity: O(N) Space Complexity: O(1)
Solution Code:
class Codec {
// Encodes a list of strings to a single string.
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for(String s : strs) {
sb.append(s.length()).append('*').append(s);
}
return sb.toString();
}
// Decodes a single string to a list of strings.
public List<String> decode(String s) {
List<String> ret = new ArrayList<String>();
int i = 0;
while(i < s.length()) {
int slash = s.indexOf('*', i);
int size = Integer.valueOf(s.substring(i, slash));
ret.add(s.substring(slash + 1, slash + size + 1));
i = slash + size + 1;
}
return ret;
}
}