784. Letter Case Permutation

Loading...
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

英数字の文字列が与えられ、アルファベットを大文字小文字に変換した際の全パターンを列挙する問題。

数字は変換しないので、アルファベットかどうかで場合分けしながら効率的な全探索を考える。

再帰

文字列を先頭から1つずつ見ていき、アルファベットだった場合は小文字と大文字を付け加えた文字列を作成する。

例えばA1bという文字列が与えられた場合、

1.最初の1文字目はアルファベットなのでaとAが回答候補になる。

2.2文字目は数字なのでそのまま追加:a1、A1

3.3文字目はアルファベットなのでbとBを追加:a1b、a1B、A1b、A1B

以上の方針を実装する。

初めはからの文字列から開始し、1文字ずつ追加する。

1つのリストに回答候補を追加していくので、リストの末尾何個を持ち越すのかカウントする変数を設定する。

1つずつの文字に対して回答候補全てに文字を追加していく2重ループになる。

与えられる文字列の長さをNとすると、最初のループがO(N)、文字の追加が大文字小文字の2通りを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全探索で数え上げ、文字を1つずつ処理していく。

パターンの列挙にO(2^N)、1文字ずつ処理するため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
                                 

コメント

タイトルとURLをコピーしました