Replace Spaces

1. Problem Description

Implement a function that replaces every space in a string with “%20”. For example, when the string is We Are Happy., the result after replacement is We%20Are%20Happy.

2. Approach

• Brute force
• Preallocate space: allocate the required space before traversing to avoid creating small strings

3. Implementation

3.1. Brute Force

// Brute force
// Time: O(n)
// Space: O(n)
func ReplaceSpace(s string) string {
	if s == "" {
		return ""
	}

	res := ""
	for _, ch := range s {
		if string(ch) == " " {
			res += "%20"
			continue
		}
		res += string(ch)
	}

	return res
}

3.2. Preallocate Memory

// Preallocate memory
// Time: O(n)
// Space: O(n)
func ReplaceSpace(s string) string {
	if s == "" {
		return ""
	}

	count := 0
	for _, ch := range s {
		if ch == ' ' {
			count++
		}
	}

	res := make([]byte, 0, count*2+len(s))
	for i := 0; i < len(s); i++ {
		if s[i] == ' ' {
			res = append(res, '%', '2', '0')
			continue
		}

		res = append(res, s[i])
	}
	return string(res)
}

4. References

• Replace Spaces - NowCoder