strs the input list
Encoded blue = length digits and #, the rest is payload
"" (nothing to encode)
Decoded res, rebuilt from the encoded string alone
public class Codec { public String encode(List<String> strs) { StringBuilder res = new StringBuilder(); for (String s : strs) { res.append(s.length()).append('#').append(s); } return res.toString(); } public List<String> decode(String s) { List<String> res = new ArrayList<>(); int i = 0; while (i < s.length()) { int j = i; while (s.charAt(j) != '#') { j++; } int length = Integer.parseInt(s.substring(i, j)); res.add(s.substring(j + 1, j + 1 + length)); i = j + 1 + length; // jump past the payload } return res; }}
- i
- —
- j
- —
- length
- —
- encoded
- ""
- res
- —
Why it works
- The naive idea joins with a separator such as
","and splits on it. It breaks the moment a string contains that separator, and escaping every character works but is fiddly to get right. - Say how long, then say what. Each string is written as its length, a
#, then the raw characters. The decoder reads digits up to the first#, then takes exactlylengthcharacters without looking at them, so a#or a digit inside the payload is harmless. - Why O(n): encoding writes each character once plus a few header characters per string. Decoding visits each header character once and jumps over each payload with one
substring. - Pitfall: do not search for the next
#from the start of the payload, and do not assume one-digit lengths.Integer.parseInt(s.substring(i, j))reads"12"as twelve. - Empty strings survive:
""encodes as"0#", which is different from an empty list (""). A plain separator cannot tell those apart.