[leetcode]PythonおよびTrieツリーによる[14.最長共通プレフィックス]

原題
文字列配列の最長の共通接頭辞を検索する関数を作成します.
共通の接頭辞が存在しない場合は、空の文字列「」を返します.
例1:入力:[[flower]、[flow]、[flight]]出力:[fl]
例2:入力:["dog","racecar","car"]出力:""
説明:入力に共通接頭辞は存在しません.
Trieツリーによる実装

class TrieNode(object):
#   Python  Trie   
    def __init__(self):
        self.child = {}
        self.flag = None


class Solution(object):
    def __init__(self):
        self.root = TrieNode()
        
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if strs == []:
            return ''
        elif len(strs) == 1:
            return strs[0]
        
        for words in strs:        #  strs        Trie 
            curNode = self.root    
            for word in words:
                if curNode.child.get(word) is None:
                    nextNode = TrieNode()
                    curNode.child[word] = nextNode
                curNode = curNode.child[word]
            curNode.flag = 1
        
        curNode = self.root
        
        lcp = []
        while curNode.flag != 1:    #   Trie ，               1
            if len(curNode.child) == 1:
                lcp.append(list(curNode.child.keys())[0])
                curNode = curNode.child[list(curNode.child.keys())[0]]
            else:
                break
        return ''.join(lcp)

Trieツリーの簡略化

はTrie数の簡略化版に相当し、ツリーを構築する操作

を省いただけだ.

zipを利用してstrsのすべての要素対応ビットを1つのlistにパッケージ化し、set()を利用してこのlistを再削除すると、残りの数は重複しない文字の個数であり、1であれば共通接頭辞の1つを表し、

を下に遍歴し続ける.

例えば、「flower」、「flow」、「flight」、zip(*strs)と入力した結果、[‘f’,‘f’,‘f’,[‘l’,‘l’,‘l’],[‘o’,‘o’,‘i’],[‘w’,‘w’,‘g’],set()後の結果は、それぞれ[‘f’,[‘l’],[‘l’,[‘o’,‘i’,[‘w’,‘g’]]

である

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if strs == []:
            return ''
        elif len(strs) == 1:
            return strs[0]
        
        lcp= ""
        for each in zip(*strs):
            if len(set(each)) == 1:
                lcp += each[0]
            else:
                return lcp
        return lcp