LeetCode #271. Encode and Decode Strings

Time Complexity: O(n)

for encoding:

• Each character of each string is appended once
• StringBuilder.append() is amortized O(1) per char
• Total work = proportional to total characters

for decoding:

• Pointer i only moves forward
• Each character is visited a constant number of times
• No backtracking or nested re-scanning

Space Complexity: O(n)

You must store:

• encoded string (encode)
• decoded list of strings (decode)

That’s O(n) by necessity

Extra (auxiliary) space

• Only a few integers and pointers → O(1)

class Solution {

    // 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) {
        //create a list of String to return tthe result
        List<String> result = new ArrayList<>();
        // overall string pointer
        int i = 0;

        while (i < s.length()) {
            // pointer to find the delimiter '#'
            int j = i;
            while (s.charAt(j) != '#') {
                j++;
            }

            // parse length
            int length = Integer.parseInt(s.substring(i, j));

            // extract string
            String str = s.substring(j + 1, j + 1 + length);
            result.add(str);

            // move pointer
            i = j + 1 + length;
        }

        return result;
    }
}