Task04: String

1. Video title

1.1 Verify the palindrome string

1.1.1 describe

Given a string , Verify that it is a palindrome string , Consider only alphabetic and numeric characters , The case of letters can be ignored .

explain ： In this question , We define an empty string as a valid palindrome string .

Example 1:

Input : “A man, a plan, a canal: Panama”
Output : true
explain ：“amanaplanacanalpanama” It's a palindrome string

Example 2:

Input : “race a car”
Output : false
explain ：“raceacar” It's not a palindrome string

Tips ：

1 <= s.length <= 2 * 105
character string s from ASCII Character composition

1.1.2 Code

In theory, it should be double pointer , One in front, one in back , Start scanning at the same time

If you encounter letters, you will compare , Continue scanning the same , If it is different, it will jump out and report an error

If you encounter spaces or commas , Continue to scan down directly , Stop and compare when you encounter letters

It is necessary to pay attention to python Language for the use of several functions of the character bed

isdigit It's a pure number ,isalpha It's pure letters ,isalnum It's a mixture of numbers and letters

If isalnum It is also true to encounter a string of pure numbers or pure letters alone True

The following solution is ingenious , Take the letters directly , Then reverse the contrast , Because palindromes are the same

class Solution:
    def isPalindrome(self, s: str) -> bool:
        sgood = "".join(ch.lower() for ch in s if ch.isalnum())
        return sgood == sgood[::-1]

1.1.3 summary

isdigit It's a pure number ,isalpha It's pure letters ,isalnum It's a mixture of numbers and letters

If isalnum It is also true to encounter a string of pure numbers or pure letters alone True

Palindrome strings are the same , So you can directly reverse the string and use API Compare

1.2 Flip the words in the string

1.2.1 describe

Give you a string s , Flip all in the string one by one word .

word Is a string of non whitespace characters .s Use at least one space in the string word Separate .

Please return to a flip s A string in word order and connected by a single space .

explain ：

Input string s It can be in the front 、 Contain extra spaces after or between words .
After flipping, the words should be separated by only one space .
The flipped string should not contain additional spaces .

Example 1：

Input ：s = “the sky is blue”
Output ：“blue is sky the”

Example 2：

Input ：s = " hello world "
Output ：“world hello”
explain ： The input string can contain extra spaces before or after , However, the flipped characters cannot include .

Example 3：

Input ：s = “a good example”
Output ：“example good a”
explain ： If there are extra spaces between two words , Reduce the space between words after flipping to only contain one .

Example 4：

Input ：s = " Bob Loves Alice "
Output ：“Alice Loves Bob”

Example 5：

Input ：s = “Alice does not even like bob”
Output ：“bob like even not does Alice”

Tips ：

1 <= s.length <= 104
s Contains English upper and lower case letters 、 Numbers and spaces ’ ’
s in There is at least one word

Advanced ：

Please try using O(1) In situ solution of extra space complexity .

1.2.2 Code

If you use extra space , It should be to build a stack , Then scan the original array

Start from scratch , Remove extra space , When you encounter a space again, it proves that the word ends

Then push the word onto the stack , Continue to scan other words in the original array

Wait until all scans are complete , Take the elements from the top of the stack in turn , Connect with spaces

If you use API Words , Namely split() Again reversed

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(reversed(s.split()))

1.2.3 summary

In many languages API All support join、split() and reversed

2. Assignment topic

2.1 Verify palindrome string Ⅱ

2.1.1 describe

Given a non empty string s, Delete at most one character . Determine whether it can be a palindrome string .

Example 1:

Input : s = “aba”
Output : true

Example 2:

Input : s = “abca”
Output : true
explain : You can delete c character .

Example 3:

Input : s = “abc”
Output : false

Tips :

1 <= s.length <= 105
s It's made up of lowercase letters

2.1.2 Code

The idea basically continues the above verification palindrome string , The only condition is that one character can be deleted

That is when the characters are not equal , Delete left and right respectively , See which operations might be equal

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def checkPalindrome(low, high):
            i, j = low, high
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True

        low, high = 0, len(s) - 1
        while low < high:
            if s[low] == s[high]: 
                low += 1
                high -= 1
            else:
                return checkPalindrome(low + 1, high) or checkPalindrome(low, high - 1)
        return True

2.1.3 summary

The deleted character may be left or right , All have to try

2.2 Excel Table column name

2.2.1 describe

Give you an integer columnNumber , Back to it in Excel The name of the corresponding column in the table .

for example ：

A -> 1
B -> 2
C -> 3
…
Z -> 26
AA -> 27
AB -> 28
…

Example 1：

Input ：columnNumber = 1
Output ：“A”

Example 2：

Input ：columnNumber = 28
Output ：“AB”

Example 3：

Input ：columnNumber = 701
Output ：“ZY”

Example 4：

Input ：columnNumber = 2147483647
Output ：“FXSHRXW”

Tips ：

$1<=columnNumber<=2^{31}-1$

2.2.1 Code

It seems to be a problem of binary conversion , But because of a shift , The solution looks big

Suppose the column name of a column in the table is ABCD These four letters of , The meaning is as follows ：

A	B	C	D
$1\ast 26^3$	$2\ast 26^2$	$3\ast 26^1$	$4\ast 26^0$

Generally speaking , The number represented by each letter , All follow $a_i+26^{i-1}$ This format

For the usual 26 Base number ,$a_i$ The range of phi is zero 0~25, But this time it is 1~26, Yes 1 Bit offset

So , in other words , Remainder is 0 representative Z, Remainder is 1 representative A, So before taking the remainder -1, Correction position

Or the example above , Its value is $1\ast 26^3+2\ast 26^2+3\ast 26^1+4\ast 26^0$ , Direct pair 26 Take remainder as 4

4 It stands for D, stay 1~26 Under the circumstances , That is, for A Yes 3 Bit offset , So we need to -1

But first - Take the rest , Because it makes the remainder in 0~25 Between , Just relative to A The offset

If it is to take the remainder first and then - Words , Will make A~Z The remainder becomes 0,1...,24,-1, It is not convenient to base on A Calculate the value of letters

Every time -1 Then calculate the remainder , For the current last , This -1 It will not affect the numbers in other places

Because every letter follows $a_i+26^{i-1}$, The value given by the title columnNumber That is, the sum of this format

So every time -1, Only the rightmost $a_i$, That is to say $a_0$, Numbers that do not affect other locations

Whenever we find $a_0$ After the corresponding letter , All need to use // Remove this one , Go again -1 Calculate the new $a_0$

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        ans = list()
        while columnNumber > 0:
            columnNumber -= 1
            ans.append(chr(columnNumber % 26 + ord("A")))
            columnNumber //= 26
        return "".join(ans[::-1])

2.2.3 summary

Continue with the above example ,$a_i+26^{i-1}$,$1\ast 26^3+2\ast 26^2+3\ast 26^1+4\ast 26^0$

In this format , Even if there is an offset , That affects everyone $a_i$, And they don't affect each other

That is to say, you only need to ask for $a_0$ When ,-1 Then the remainder can be mapped to 0~25, Does not affect other bits

2.3 String decoding

2.3.1 describe

Given an encoded string , Returns the decoded string .

The coding rule is : k[encoded_string], Represents the encoded_string Just repeat k Time . Be careful k Positive integer guaranteed .

You can think that the input string is always valid ; There are no extra spaces in the input string , And the square brackets entered always meet the format requirements .

Besides , You can assume that the raw data does not contain numbers , All numbers only indicate the number of repetitions k , For example, there is no such thing as 3a or 2[4] The input of .

Example 1：

Input ：s = “3[a]2[bc]”
Output ：“aaabcbc”

Example 2：

Input ：s = “3[a2[c]]”
Output ：“accaccacc”

Example 3：

Input ：s = “2[abc]3[cd]ef”
Output ：“abcabccdcdcdef”

Example 4：

Input ：s = “abc3[cd]xyz”
Output ：“abccdcdcdxyz”

Tips ：

1 <= s.length <= 30
s By lowercase letters 、 Numbers and square brackets ‘[]’ form
s Guarantee is a It works The input of .
s The value range of all integers in is [1, 300]

2.3.2 Code

The problem is more complicated , It is mainly the case that brackets cover brackets , But let's start with the general

Suppose there are no parentheses , Then we should be divided into two parts , One is the number , One is a string

There may be more than one number , So consider reading the second digit , Carry the first digit

If you read the left parenthesis [, That is the beginning of the string , Read ] Is string termination

Repeat this time , Multiply by the string that needs to be repeated , Just connect the previous string

Now consider the topic itself , If there are parentheses, set parentheses , You should deal with the parentheses first

When you get the result in brackets , To combine with the previous number of repetitions , Repeat this string

So if there are parentheses , Then we need to remember the previous string , And the number of repetitions

When the inner bracket string is processed , Then repeat the string according to the number and splice

Brackets can also be used to cover three layers , That is, record the results first and then process them , This is the stack

In general , That is, every time I meet [ Just put Repeat the number and Previous string Pressing stack

Then deal with the situation in parentheses , That is, read the string , Read ] Then take the top of the stack , Repeat and splice

If in [ I'll meet you later [, That is to keep pressing the stack , Until I met ] Just pop up the top of the stack , End a couple []

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        #  Stack , It is used to handle the case that brackets cover brackets 
        res = ""
        #  Used to store the currently repeated string 
        multi = 0
        #  Used to store the number of string repetitions 
        for c in s:
            if c == '[':
                stack.append([multi, res])
                res, multi = "", 0
            #  The previous string , Save the number of times the string is repeated 
            elif c == ']':
                cur_multi, last_res = stack.pop()
                res = last_res + cur_multi * res
            #  Repeat this string , And concatenate the previous string 
            elif '0' <= c <= '9':
                multi = multi * 10 + int(c)
                #  If the number is more than one , Then carry superposition 
            else:
                res += c
                #  Used to store the current string 
        return res

2.3.3 summary

If the string has more than one digit , Consider reading the second digit , Carry the first digit

There are brackets and brackets , And give priority to those in brackets , Consider pushing previous data onto the stack

It sounds like an advanced version of bracket matching ,[ Pressing stack , encounter ] Just pop the top of the stack to match