Leetcode - letter-case-permutation

https://leetcode.com/problems/letter-case-permutation/

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.

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

Input: S = "3z4"
Output: ["3z4", "3Z4"]

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

Very similar to subset. So just modify the backtracking problem and then fill with extra conditions.

func letterCasePermutation(S string) []string {
    result := []string{}
    backtrack(S, &result, &[]byte{}, 0)
    return result
}

func backtrack(S string, result *[]string, tmp *[]byte, start int) {
    if len(*tmp) == len(S) {
        *result = append(*result, string(*tmp))
    }
    for i := start; i < len(S); i++ {
        s := S[i]
        if isLow(s) {
            *tmp = append(*tmp, s-32)
            backtrack(S, result, tmp, i+1)
            *tmp = (*tmp)[:len(*tmp)-1]
        }
        if isUpper(s) {
            *tmp = append(*tmp, s+32)
            backtrack(S, result, tmp, i+1)
            *tmp = (*tmp)[:len(*tmp)-1]
        }
        
        *tmp = append(*tmp, s)
        backtrack(S, result, tmp, i+1)
        *tmp = (*tmp)[:len(*tmp)-1]
    }
}

func isLow(s byte) bool {
    if (s >= 'a' && s <= 'z')  {
        return true
    }
    
    return false
}
func isUpper(s byte) bool {
    if s >= 'A' && s <= 'Z' {
        return true
    }
    
    return false
}

• 相关文章
• 全局相关文章