784. Letter Case Permutation

LeetCode 784. Letter Case Permutation****

Description

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. You can return the output in any order.

Example 1:

Input: S = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2:

Input: S = "12345"
Output: ["12345"]

Constraints:

• S will be a string with length between 1 and 12.

• S will consist only of letters or digits.

Tags

Backtracking

Solution

Explanation for Solution 1: Traverse the string, if it is a numeric character, just append it to every candidate string, otherwise copy every candidate string and append the lower and upper alphabet to both copies respectively.

Complexity

• Time complexity: $O(2^n*n)$

• Space complexity: $O(2^n*n)$

Code

Solution 1 - Iteration:

func letterCasePermutation(S string) []string {
	bytes := make([][]byte, 1)
	for i := 0; i < len(S); i++ {
		lower, upper, isAlpha := getLowerAndUpper(S[i])
		if !isAlpha {
			for j := 0; j < len(bytes); j++ {
				bytes[j] = append(bytes[j], S[i])
			}
			continue
		}
		for j, n := 0, len(bytes); j < n; j++ {
			temp := append([]byte{}, bytes[j]...)
			bytes = append(bytes, temp)
			bytes[j] = append(bytes[j], lower)
			bytes[n+j] = append(bytes[n+j], upper)
		}
	}
	ans := make([]string, 0, len(bytes))
	for _, b := range bytes {
		ans = append(ans, string(b))
	}
	return ans
}

func getLowerAndUpper(c byte) (byte, byte, bool) {
	if c >= 65 && c <= 90 {
		return c + 32, c, true
	}
	if c >= 97 && c <= 122 {
		return c, c - 32, true
	}
	return c, c, false
}

Solution 2 - Backtracking:

func letterCasePermutation(S string) []string {
	var ans []string
	dfs(&ans, 0, []byte{}, S)
	return ans
}

func dfs(ans *[]string, index int, path []byte, S string) {
	if index == len(S) {
		*ans = append(*ans, string(path))
		return
	}
	for i := index; i < len(S) && len(path) < len(S); i++ {
		lower, upper, isAlpha := getLowerAndUpper(S[i])
		if !isAlpha {
			path = append(path, S[i])
			dfs(ans, index+1, path, S)
			break
		}
		path = append(path, lower)
		dfs(ans, index+1, path, S)
		path = path[:len(path)-1]
		path = append(path, upper)
		dfs(ans, index+1, path, S)
	}
}

func getLowerAndUpper(c byte) (byte, byte, bool) {
	if c >= 65 && c <= 90 {
		return c + 32, c, true
	}
	if c >= 97 && c <= 122 {
		return c, c - 32, true
	}
	return c, c, false
}

Reference

1. 字母大小写全排列