784.md

Is Graph Bipartite?

Description

link

---

Solution

• See Code

---

Code

最坏情况：O(n^2)

class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        res = []
        self.dfs("", S, res)
        return res

    def dfs(self, pre, s, res):
        if s == '':
            res.append(pre)
            return
        if s[0].isdigit():
            self.dfs(pre + s[0], s[1:], res)
        else:
            self.dfs(pre + s[0].lower(), s[1:], res)
            self.dfs(pre + s[0].upper(), s[1:], res)