Strings are often used with other data types

array

String subscripts are naturally arrays

Stack

Last in first out, including string problems such as bracket matching and path splitting. Note that the stack in python uses the append and pop of list to realize the push in and pop-up of stack.

Hashtable

It is mainly used for fast matching

queue

fifo

String method

• Get string length: len(str)
• Judge whether the strings are equal: str== str2
• Get substring of string: str[begin: end:step]
• Split string: str.split (regex, maxplit)
• Get subscript: python only has index()
• Case conversion: lower() upper()
• Returns the character of the specified subscript: str[i]

 

Sword finger Offer II 014 Anagrams in strings

Title Description

Given the two strings s1 and s2, write a function to determine whether s2 contains an anamorphic word of s1.

In other words, one of the permutations of the first string is a substring of the second string.

Sword finger Offer II 014 An anamorphic word in a string - LeetCode (LeetCode CN. Com)

Problem solution

Sliding fixed size window, double pointer

You can do it with character statistics, traversing s2 once

def checkInclusion(self, s1: str, s2: str) -> bool:
    arr1, arr2, lg = [0] * 26, [0] * 26, len(s1)
    if lg > len(s2):
        return False
    # Maintain a arr2, Make it in s2 Slide up and right until you touch your tail
    for i in range(lg):
        arr1[ord(s1[i]) - ord('a')] += 1
        arr2[ord(s2[i]) - ord('a')] += 1

    for j in range(lg, len(s2)):
        if arr1 == arr2:
            return True
        arr2[ord(s2[j - lg]) - ord('a')] -= 1
        arr2[ord(s2[j]) - ord('a')] += 1
    return arr1 == arr2

Sword finger Offer II 015 All modifiers in the string

Title Description

Given two strings ， s ， and ， p, find the substrings of the ， modifier ， of all ， p ， in ， s ， and return the starting indexes of these substrings. The order in which answers are output is not considered.

An anagram {refers to a string with the same letters but arranged differently

Sword finger Offer II 015 All modifiers in the string - LeetCode (LeetCode CN. Com)

Problem solution

Fixed window double pointer

Change the previous question:

def findAnagrams(self, s: str, p: str) -> List[int]:
    arr1, arr2, lg = [0] * 26, [0] * 26, len(p)
    ret = []
    if lg > len(s):
        return []
    # Maintain a arr2, Make it in s2 Slide up and right until you touch your tail
    for i in range(lg):
        arr1[ord(p[i]) - ord('a')] += 1
        arr2[ord(s[i]) - ord('a')] += 1

    for j in range(lg, len(s)+1):
        if arr1 == arr2:
            ret.append(j-lg)
        if j<len(s):
            arr2[ord(s[j - lg]) - ord('a')] -= 1
            arr2[ord(s[j]) - ord('a')] += 1
    return ret

Sword finger Offer II 016 Longest substring without duplicate characters

Title Description

Given a string ， s, please find out the length of ， the longest continuous substring ， which does not contain repeated characters.

Sword finger Offer II 016 Longest substring without repeated characters - LeetCode (leetcode-cn.com)

Problem solution

Double pointer + hash table

Double pointers. Maintain a dictionary. key is the character and value is the last position where the character was encountered

def lengthOfLongestSubstring(self, s: str) -> int:
    # Double pointer+hash surface
    dic, res, i = {}, 0, -1
    for j in range(len(s)):
        if s[j] in dic:
            i = max(dic[s[j]], i) # Update left pointer i
        dic[s[j]] = j # Hash table record
        res = max(res, j - i) # Update results
    return res

Dynamic programming dp

The dynamic programming list dp, dp[j] represents the length of the "longest non repeating substring" ending with the character s[j]. So only one for loop is needed

def lengthOfLongestSubstring(self, s: str) -> int:
        #dynamic programming+hash Table dynamic programming list dp ，dp[j]    That is to say, the character s[j] Is the length of the longest non repeating substring at the end. But as long as max, Only one variable is needed for dynamic planning, and additional space is needed
        dic = {} #record s[i] of i  s[i] For distance s[j]The nearest character is s[i]=s[j] i<j
        
        tmp = 0
        res = 0
        for j in range(len(s)):
            i = dic.get(s[j],-1) #Get index i  parameter-1 It means to return if it cannot be found-1
            dic[s[j]] = j
            if tmp < j-i:  #tmp What's in it dp[j-1]  I.e. current( shangyige)Character dp[value]
                tmp = tmp+1
            else:
                tmp = j-i
            res = max(res,tmp)  # max(dp[j-1],dp[j])
        return res