pythonでleetcode【3】を書く--有効なアルファベット異位語(242)、Trie(接頭辞ツリー)を実現する(208)

文書ディレクトリ

有効なアルファベット異位語(242)

題

構想

コード

Trie(プレフィックスツリー)(208)

を実装

題

構想

コード

有効なアルファベット異位語(242)
タイトル
2つの文字列sとtを与え、tがsのアルファベット異位語であるか否かを判断する関数を記述する.
例1:
入力:s=「anagram」、t=「nagaram」出力:true例2:
入力:s=「rat」、t=「car」出力:false説明:文字列に小文字のみが含まれていると仮定できます.
構想
簡単です.アルファベットの回数が同じかどうかを統計します.
コード#コード#

     class Solution:
        def isAnagram(self, s: str, t: str) -> bool:
            s1=[0]*26
            s2=[0]*26
            for i in s:
                s1[ord(i)-ord('a')]+=1
            
            for i in t:
                s2[ord(i)-ord('a')]+=1
            
            for i in range(26):
                if s1[i]==s2[i]:
                    pass
                else:
                    return False
            
            return True

Trie(プレフィックスツリー)の実装(208)
タイトル
Insert,search,startsWithの3つの動作を含むTrie(接頭辞ツリー)を実現する.
例:
Trie trie = new Trie();
trie.insert(“apple”); trie.search(“apple”);//を返します.search(“app”);//false trieを返します.startsWith(“app”);//を返します.insert(“app”); trie.search(“app”);//trueの説明を返します.
すべての入力が小文字a-zで構成されていると仮定できます.すべての入力が空でない文字列であることを保証します.
構想
各ノードが「a」-「z」26文字のサブノードと「flag」ノードを含み、ここで終了したときに挿入された単語であるかどうかを判断するために27フォークツリーを構築する.Insertプロシージャ:各アルファベットがツリー構造で伝達されるのを便利にし、なければ新規に作成し、最後のアルファベットになると、そのノードにキーflagを挿入して挿入された単語であることを記録します.searchプロセスは,与えられた単語に従ってツリーに深く入り込み,最後のアルファベットに遍歴できれば,このときのnodeにflagキーが含まれているかどうかを判断し,説明が含まれていれば検索できる.startwithプロシージャは,入力した単語を遍歴できる限り,この単語からstartwithがあることを説明する.
コード#コード#

    class Trie:
        
     
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.root = {}
            
     
        def insert(self, word):
            """
            Inserts a word into the trie.
            :type word: str
            :rtype: void
            """
            node = self.root
            for c in word:
                if  c not in node:
                    node[c] = {}
                node = node[c]              
            node['flag'] = True
     
        def search(self, word):
            """
            Returns if the word is in the trie.
            :type word: str
            :rtype: bool
            """
            node = self.root
            for c in word:
                if not c in node:
                    return False
                node = node[c]                
            # Doesn't end here
            if 'flag'  not in node:
                return False            
            return True
     
        def startsWith(self, prefix):
            """
            Returns if there is any word in the trie that starts with the given prefix.
            :type prefix: str
            :rtype: bool
            """
            node = self.root
            for c in prefix:
                if not c in node:
                    return False
                node = node[c]    
            return True

     Your Trie object will be instantiated and called as such:
     obj = Trie()
     obj.insert(word)
     param_2 = obj.search(word)
     param_3 = obj.startsWith(prefix)
`