Just a moment...
leetcode.com
英数字の文字列が与えられ、アルファベットを大文字小文字に変換した際の全パターンを列挙する問題。
数字は変換しないので、アルファベットかどうかで場合分けしながら効率的な全探索を考える。
再帰
文字列を先頭から1つずつ見ていき、アルファベットだった場合は小文字と大文字を付け加えた文字列を作成する。
例えばA1bという文字列が与えられた場合、
１．最初の1文字目はアルファベットなのでaとAが回答候補になる。
２．２文字目は数字なのでそのまま追加：a1、A1
３．３文字目はアルファベットなのでbとBを追加：a1b、a1B、A1b、A1B
以上の方針を実装する。
初めはからの文字列から開始し、１文字ずつ追加する。
１つのリストに回答候補を追加していくので、リストの末尾何個を持ち越すのかカウントする変数を設定する。
１つずつの文字に対して回答候補全てに文字を追加していく２重ループになる。
与えられる文字列の長さをNとすると、最初のループがO(N)、文字の追加が大文字小文字の２通りをN文字行うのでO(2^N)となり、トータルの計算量はO(N * 2^N)。
class Solution:
def letterCasePermutation(self, s: str) -> List[str]:
ans=[""]
for char in s:
n=len(ans)
cnt=0
for i in range(n):
temp = ans[i]
if char.isalpha():
ans.append(temp+char.lower())
ans.append(temp+char.upper())
cnt+=2
else:
ans.append(temp+char)
cnt+=1
ans=ans[-cnt:]
return ans
bit全探索
大文字にするか、小文字にするかの二択なので、bit全探索が使える。
どの文字列を変更するかをbit全探索で数え上げ、文字を１つずつ処理していく。
パターンの列挙にO(2^N）、１文字ずつ処理するためO(N)で、トータルO(N * 2^N）となる。
答えが被る可能性があるため、最後にsetを取って提出。
class Solution:
def letterCasePermutation(self, s: str) -> List[str]:
n = len(s)
ans = []
for i in range(2**n):
pattern = [0] * n
for j in range(n):
if i>>j & 1:
pattern[j]=1
temp = ""
for j in range(n):
if not pattern[j]:
temp += s[j]
else:
if s[j].isalpha():
if s[j].islower():
temp += s[j].upper()
else:
temp += s[j].lower()
else:
temp += s[j]
ans.append(temp)
ans = list(set(ans))
return ans
コメント