# 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