データ構造とアルゴリズム分類の練習-辞書文字列

辞書はPython言語で唯一のマッピングタイプです.書式:

d = {key1 : value1, key2 : value2 }

マッピングタイプのオブジェクトにおけるハッシュ値(キー,key)と指向するオブジェクト(値,value)は一対多の関係であり,通常は可変ハッシュテーブルと考えられる.辞書オブジェクトは可変で、任意の数のPythonオブジェクトを格納できるコンテナタイプであり、他のコンテナタイプも含まれます.
ディクショナリタイプとシーケンスタイプ(リスト、メタグループ)の違いは、データへのアクセスとアクセスの仕方が異なることです.1.シーケンスタイプは数値タイプのキーのみを使用します(シーケンスの開始から数値順に索引付けします).マッピングタイプは、他のオブジェクトタイプをキーとして使用できます.一般的に最も一般的なのは文字列をキーとして使用します.2.シーケンスタイプのキーとは異なり、マッピングタイプのキーは、格納データ値に直接または間接的に関連付けられる.3.マッピング・タイプのデータは無秩序に配列され、シーケンス・タイプは数値的に配列されています.-pythonコアプログラミングから抜粋します.
Word Pattern語モード
Given a pattern and a string str, find if str follows the same pattern.
Examples:

pattern = "abba", str = "dog cat cat dog" should return true.

pattern = "abba", str = "dog cat cat fish" should return false.

Notes:

Both pattern and str contains only lowercase alphabetical letters.

Both pattern and str do not have leading or trailing spaces.

Each word in str is separated by a single space.

Each letter in pattern must map to a word with length that is at least 1.

パターン文字列の各文字と単語文字列の各単語間のマッピングを確立します.最初の文字から、まずハッシュ・テーブルに表示されるかどうかを確認し、表示されると、そのマッピングされた単語がこの時点で対応する単語でなければfalseを返します.ハッシュ・テーブルに表示されない場合は、新しく出会った単語がハッシュ・テーブルのマッピングであるかどうかを確認し、そうであればfalseを返します.

class Solution(object):
    def wordPattern1(self, pattern, str):
        words = str.split(' ')
        dic = {}
        used = set()
        
        # key: patter 
        # value: word_str
        if len(words) != len(pattern):
            return False 
        if not words and not pattern:
            return True  
        for i in range(len(pattern)):
            if pattern[i] not in dic:
                dic[pattern[i]] = words[i]
                if words[i] in used:
                    return False
                used.add(words[i])
            if dic[pattern[i]] != words[i]:
                return False           
        return True

Longest Substring Without Repeating Characters最長重複文字なしサブストリング
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
longest,offset,n,indexをそれぞれ現在最長文字列,オフセット量(最小値),文字カウント,重複文字辞書なしとして定義する.最初から遍歴し、現在の文字が辞書に含まれていない場合は追加します.辞書では座標が更新され、元の座標がオフセット量よりも大きい場合は、longestとoffsetを更新する必要がある繰り返し文字が発生したことを示します.ループが完了したらlongestを更新すればいいです.

class Solution:
    # @return an integer
    def lengthOfLongestSubstring(self, s):
        str_len = len(s)
        if str_len <= 1:
            return str_len
        if str_len == 2:
            return 1 if s[0] == s[1] else 2
        longest, offset, n, index = 0, 0, 0, {}
        for ch in s:
            if ch in index and index[ch] >= offset:
                longest = max(n - offset, longest)
                offset = index[ch] + 1
            index[ch] = n
            n += 1   
        longest = max(n - offset, longest)
        return longest

Minimum Window Substring最小ウィンドウサブストリング
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example, S = "ADOBECODEBANC", T = "ABC"
Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
辞書needで検索する各文字と数を保存し、missingは現在のウィンドウに文字が欠けている個数を保存します.最初から遍歴し、need[c]>0が必要な文字を見つけた場合、missingとneedを更新します.欠落した文字が見つかった場合は、ウィンドウの左側の境界を右に移動し、現在の文字がTで直接省略されていない場合は、Tでウィンドウの右端で再びこの文字に遭遇する必要がある場合はスキップし、戻り範囲を比較して更新します.s[i:j]は現在のウィンドウを表し、s[I:J]は戻るウィンドウを表す.

def minWindow(self, s, t):
    need, missing = collections.Counter(t), len(t)
    i = I = J = 0
    for j, c in enumerate(s, 1):
        missing -= need[c] > 0
        need[c] -= 1
        if not missing:
            while i < j and need[s[i]] < 0:
                need[s[i]] += 1
                i += 1
            if not J or j - i <= J - I:
                I, J = i, j
    return s[I:J]

Repeated Substring Patternサブストリングパターンの繰り返し
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Input: "abab"Output: True
参照leetcode discuss
S 1=S+Sとし、S 1の1番目と最後の文字を除いてS 2を得、SがS 2に存在する場合、Sは重複サブストリング構成とする.S 1におけるSの開始位置がpであると仮定すると、S[:p]は反復サブ列である.
十分条件:S＝sy sy,S 1＝sy sy sy,S 2＝sx sy sxがSを含むとする.
必要条件:S 1におけるSの開始位置をp,s 1=S[:p],S=s 1 x 1とすると、S=s 1 x 1=x 1 s 1--(1)
ここで、len(x 1)>=len(s 1).なぜならlen(x 1)
len(x 1)=len(s 1)の場合、(1)から得られるs 1=x 1=>Sは、繰り返しサブ列からなる.
len(x 1)>len(s 1)の場合、x 1はs 1の先頭の文字列であり、x 1=s 1 x 2とし、(1)からs 1 s 1 x 2=s 1 x 2 s 1=>s 1 x 2=x 2 s 1--(2)
同様に、len(x 2)>=len(s 1).(1)(2)から分かるように、S=s 1 s 1 x 2=x 2 s 1 s 1、len(x 2)
このように反復すると、最終的にlen(xn)=len(s 1)となり、s 1 xn=xns 1=>xn=s 1=>S=s 1 x 1=s 1 s 1 x 2=...=s1s1...s 1 xn=>Sは、繰り返しサブ列からなる.

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return False
        return str in (2 * str)[1:-1]

Validate IP Address認証IPアドレス
区切り文字、フィールド数、フィールド長、文字範囲、フィールドフォーマットについてそれぞれ判断します.

class Solution(object):    
    def validIPAddress(self, IP):
        def isIPv4(s):
            try: return str(int(s)) == s and 0 <= int(s) <= 255
            except: return False
            
        def isIPv6(s):
            if len(s) > 4: return False
            try: return int(s, 16) >= 0 and s[0] != '-'
            except: return False

        if IP.count(".") == 3 and all(isIPv4(i) for i in IP.split(".")): 
            return "IPv4"
        if IP.count(":") == 7 and all(isIPv6(i) for i in IP.split(":")): 
            return "IPv6"
        return "Neither"