【LeetCode】Python 3最長の共通接頭辞と有効な括弧を実現

最大共通接頭辞
文字列配列の最長の共通接頭辞を検索する関数を作成します.共通の接頭辞が存在しない場合は、空の文字列「」を返します.
例1:入力:[[flower]、[flow]、[flight]]出力:[fl]
例2:入力:[「dog」、「racecar」、「car」出力:「」解釈:入力に共通接頭辞は存在しません.
説明:すべての入力には小文字a-zのみが含まれます.
方法1:水平走査法はまずすべての文字列長の最小値min_を求めるlen、最長共通接頭辞の長さはmin_以下であるに違いないlen.最初の文字列の前min_len文字は、各文字を他のすべての文字列対応ビットの文字と順次比較し、等しくないまで終了する.

class Solution:
    def longestCommonPrefix(self, strs):
        """
        strs: list[str]
        output: str
        """
        result = ""
        if strs == []:
            return result
        if len(strs) == 1:
            return strs[0]
    
        #             
        lens = [len(s) for s in strs]
        min_len = min(lens)
                
        for i in range(min_len):  #        min_len   
            for j in range(1,len(strs)):  #    
                if strs[j][i] != strs[0][i]: 
                    return result  #      i      ，     i   
            result += strs[0][i]  #     ，        i     ，  i         。
        return result

方法2:二分ルックアップ法(数値に類比する二分ルックアップ法)

class Solution:
    #          lens   （   lens ）           
    def isCommonPrefix(self,strs,lens):
        str_com = strs[0][0:lens+1]
        for i in range(1,len(strs)):
            if strs[i][0:lens+1] != str_com:
                return False
        return True
    
    def longestCommonPrefix(self, strs):
        """
        strs: list[str]
        output: str
        """
        if strs == []:
            return ""
        if len(strs) == 1:
            return strs[0]
        
        #             
        lens = [len(s) for s in strs]
        min_len = min(lens)
        
        low = 0
        high = min_len - 1
        while low <= high:
            middle = (low + high)//2
            #   middle          
            if self.isCommonPrefix(strs,middle):
                low = middle + 1  # ，        middle  
            else:
                high = middle - 1  #  ，        middle      
        return strs[0][0:(low+high)//2 + 1]
        

有効なかっこ
‘(’,’)’,’{’,’}’,’[’,’]’のみを含む文字列を与え,文字列が有効であるか否かを判断する.
有効な文字列は次のとおりです.

左かっこは、同じタイプの右かっこで閉じる必要があります.

左かっこは正しい順序で閉じなければなりません.

注意空の文字列は有効な文字列とみなされます.
例1:入力:「()」出力:true
例2:入力:「()[]{}」出力:true
例3:入力:「(」出力:false
例4:入力:「([)]出力:false
例5:入力:{[]}出力:true
公式の解題:思想は有効な式のサブ式も有効な式であるべきで、以下の図:式の中で1対の一致する括弧に出会うたびに、式からそれを削除して、最後に1つの空の文字列を残します.
アルゴリズムは次のとおりです.

初期化スタックS

式は、式の各括弧を順次処理する.

カッコが付いている場合は、スタックに押すだけです.これは、後で処理し、前のサブエクスプレッションに簡単に移動することを意味します.

閉じたカッコに遭遇した場合、スタックの上部の要素をチェックします.スタックの上部の要素が同じタイプの左かっこである場合、スタックからポップアップして処理を続行します.それ以外の場合、これは式が無効であることを意味します.

最後に残りのスタックに要素が残っている場合、これは式が無効であることを意味します.

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []  #         
        mapping = {")": "(", "}": "{", "]": "["}#           ，           
        for char in s:
            if char in mapping:  #  char      
                #  stack  ，  stack        ，stack    top_element  '#'
                top_element = stack.pop() if stack else '#'  
                #char      char      ，       ，          ，  False
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)  #char    ，    

        #for    ，                ，         ，
        #     ，           ，           。
        return not stack