Encode and Decode Strings

Medium

The problem

Build a Codec with two methods. Encode turns a list of words into ONE single string, and Decode takes that string and gives back exactly the original list of words. The words can hold any characters, including digits, spaces and symbols, and can even be empty.

Example 1
Input: c := Codec{} s := c.Encode([]string{"hello", "", "a#b"}) c.Decode(s)
Output: ["hello", "", "a#b"]
Decode must rebuild the exact same three words, including the empty one and the one that contains a #. What the encoded string s looks like is up to you.
Example 2
Input: s := c.Encode([]string{}) c.Decode(s)
Output: []
An empty list must come back as an empty list.

Limits

0 ≤ strs.length ≤ 200
0 ≤ strs[i].length ≤ 200
Words may contain any ASCII character
Decode only ever receives a string made by your own Encode

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Any separator character could also appear inside a word. How can the decoder know where a word ends?

The idea

Prefix each word with its length and a delimiter, like "5#hello". When decoding, read the number, skip the delimiter, then take exactly that many characters.

Target: O(total characters) time and space

Go function shape

type Codec struct{}
func (c *Codec) Encode(strs []string) string
func (c *Codec) Decode(s string) []string

Reference solution

Tested with go test. Try it yourself first, then compare.

// Encode writes each word as "<length>#<word>". The length tells the decoder exactly where the word ends,
// so the word itself may contain any character, including "#" and digits.
func Encode(strs []string) string {
	var sb strings.Builder
	for _, s := range strs {
		sb.WriteString(strconv.Itoa(len(s)))
		sb.WriteByte('#')
		sb.WriteString(s)
	}
	return sb.String()
}

func Decode(s string) []string {
	out := []string{}
	for i := 0; i < len(s); {
		j := i
		for s[j] != '#' {
			j++ // read the length digits up to the first '#'
		}
		n, _ := strconv.Atoi(s[i:j])
		out = append(out, s[j+1:j+1+n])
		i = j + 1 + n
	}
	return out
}

Read the lesson: Arrays & Hash Map