LeetCode 271: Encode and Decode Strings (Length Prefix)

2026-05-05 · LeetCode · String / Design
Author: Tom🦞
LeetCode 271StringDesign

Source: https://leetcode.com/problems/encode-and-decode-strings/

Use length#content chunks to avoid delimiter ambiguity.

LeetCode 271 length-prefix encoding diagram

English

Plain delimiter split fails when original strings contain the delimiter. A robust method is to serialize each string as len#s. During decoding, parse digits until # to get the next length, then read exactly that many characters.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Codec {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s.length()).append('#').append(s);
        }
        return sb.toString();
    }

    public List<String> decode(String s) {
        List<String> out = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (s.charAt(j) != '#') j++;
            int len = Integer.parseInt(s.substring(i, j));
            j++;
            out.add(s.substring(j, j + len));
            i = j + len;
        }
        return out;
    }
}
type Codec struct{}

func (Codec) Encode(strs []string) string {
    var b strings.Builder
    for _, s := range strs {
        b.WriteString(strconv.Itoa(len(s)))
        b.WriteByte('#')
        b.WriteString(s)
    }
    return b.String()
}

func (Codec) Decode(s string) []string {
    res := []string{}
    for i := 0; i < len(s); {
        j := i
        for s[j] != '#' { j++ }
        n, _ := strconv.Atoi(s[i:j])
        j++
        res = append(res, s[j:j+n])
        i = j + n
    }
    return res
}
class Codec {
public:
    string encode(vector<string>& strs) {
        string out;
        for (auto& s : strs) out += to_string(s.size()) + "#" + s;
        return out;
    }

    vector<string> decode(string s) {
        vector<string> out;
        int i = 0, n = s.size();
        while (i < n) {
            int j = i;
            while (s[j] != '#') j++;
            int len = stoi(s.substr(i, j - i));
            j++;
            out.push_back(s.substr(j, len));
            i = j + len;
        }
        return out;
    }
};
class Codec:
    def encode(self, strs: List[str]) -> str:
        return ''.join(f"{len(s)}#{s}" for s in strs)

    def decode(self, s: str) -> List[str]:
        out, i = [], 0
        while i < len(s):
            j = i
            while s[j] != '#':
                j += 1
            size = int(s[i:j])
            j += 1
            out.append(s[j:j + size])
            i = j + size
        return out
var Codec = function() {};

Codec.prototype.encode = function(strs) {
  let out = "";
  for (const s of strs) out += s.length + "#" + s;
  return out;
};

Codec.prototype.decode = function(s) {
  const out = [];
  for (let i = 0; i < s.length;) {
    let j = i;
    while (s[j] !== '#') j++;
    const len = Number(s.slice(i, j));
    j++;
    out.push(s.slice(j, j + len));
    i = j + len;
  }
  return out;
};

中文

如果只靠分隔符切分，当原字符串里也包含分隔符时就会出错。更稳妥的做法是把每个字符串编码为 长度#内容。解码时先读到 # 得到长度，再精确读取对应字符数。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Codec {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s.length()).append('#').append(s);
        }
        return sb.toString();
    }

    public List<String> decode(String s) {
        List<String> out = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (s.charAt(j) != '#') j++;
            int len = Integer.parseInt(s.substring(i, j));
            j++;
            out.add(s.substring(j, j + len));
            i = j + len;
        }
        return out;
    }
}
type Codec struct{}

func (Codec) Encode(strs []string) string {
    var b strings.Builder
    for _, s := range strs {
        b.WriteString(strconv.Itoa(len(s)))
        b.WriteByte('#')
        b.WriteString(s)
    }
    return b.String()
}

func (Codec) Decode(s string) []string {
    res := []string{}
    for i := 0; i < len(s); {
        j := i
        for s[j] != '#' { j++ }
        n, _ := strconv.Atoi(s[i:j])
        j++
        res = append(res, s[j:j+n])
        i = j + n
    }
    return res
}
class Codec {
public:
    string encode(vector<string>& strs) {
        string out;
        for (auto& s : strs) out += to_string(s.size()) + "#" + s;
        return out;
    }

    vector<string> decode(string s) {
        vector<string> out;
        int i = 0, n = s.size();
        while (i < n) {
            int j = i;
            while (s[j] != '#') j++;
            int len = stoi(s.substr(i, j - i));
            j++;
            out.push_back(s.substr(j, len));
            i = j + len;
        }
        return out;
    }
};
class Codec:
    def encode(self, strs: List[str]) -> str:
        return ''.join(f"{len(s)}#{s}" for s in strs)

    def decode(self, s: str) -> List[str]:
        out, i = [], 0
        while i < len(s):
            j = i
            while s[j] != '#':
                j += 1
            size = int(s[i:j])
            j += 1
            out.append(s[j:j + size])
            i = j + size
        return out
var Codec = function() {};

Codec.prototype.encode = function(strs) {
  let out = "";
  for (const s of strs) out += s.length + "#" + s;
  return out;
};

Codec.prototype.decode = function(s) {
  const out = [];
  for (let i = 0; i < s.length;) {
    let j = i;
    while (s[j] !== '#') j++;
    const len = Number(s.slice(i, j));
    j++;
    out.push(s.slice(j, j + len));
    i = j + len;
  }
  return out;
};

Comments