String notes

character string （String）

String related concepts

java：String Built in type , Reference data type , Non modifiable , If you want to change, consider StringBuffer,StringBuilder,char[]
C++：std::string Changeable , It can also be used. char
C： Only char[]
It should be noted that ：
1、C++ in "+" Operator complexity undefined , But it is generally considered to be linear .
2、 stay C++ in std::string substr and java Medium String Of subString Different parameters .
3、 character in range ：
C/C++[-128,127] It usually translates into undesigned[0,255]（ Platform related ）
java[0,65535]（ Platform related ）

Here are some examples of string related interview questions .

example 1,0-1 In exchange for

Put one 0-1 strand （ Contains only 0 and 1 String of ） Sort , You can exchange any two positions , Ask the minimum number of exchanges ？
analysis ： Use fast platoon partition？？ The leftmost 0 And the rightmost 1 Don't worry about it
such as 000…000001011…111111111

// Part of the code is as follows 
int answer=0;
for(int i=0,j=len-1;i<j;++i,--j){
    
	for(;(i<j)&&(a[i]=='0');++i);
	for(;(j>i)&&(a[j]=='1');--j);
	if(i<j) ++answer;
}

example 2, String replacement and copying

Delete a string and all a, And copy all b. notes ： The character array is large enough （ Don't open up new space ）
analysis ： Delete first a, You can use the space of the original string

// Delete first a, You can use the space of the original string 
int n=0,numb=0;
for(int i=0; s[i]; i++){
    
	if(s[i] != 'a'){
    s[n++] == s[i];}
	if(s[i] == 'b'){
    ++numb;}
}
s[n]=0;
// Copy again b, Note that the string should be lengthened 
int newLength = n+numb;
s[newLength]=0;
for(int i=newLength-1,j=n-1;j>=0;--j){
    
	// Here we use the reverse copy method , The original information will not be overwritten , Keep the original information unchanged 
	s[i--]=s[j];
	if(s[j]=='b') s[i--]='b';
}

This question adopts a conventional technique **“ Copy backwards ”**(memery copy), It can ensure that the original information will not be overwritten .

example 3、 Exchange asterisks

A string contains only * Number and number , Please put all its asterisks at the beginning .
analysis ：
Method 1： Quick line up partition— The relative order of numbers will change
Loop invariants ：[0,i-1] All are asterisk ,[i,j-1] It's all numbers ,[j,n-1] Not detected .

for(int i=0,j=0;j<n;++j){
    
	if(s[j]=='*') swap(s[i++],s[j]);
}

Method 2： use “ Copy backwards ”, The relative order of numbers remains unchanged

int j=n-1;
for(int i=n-1;i>=0;--i){
    
	if(isdigit(s[i])) {
    
		s[j--]=s[i];// If i It's the number. , Then copy to j; If i yes * Number , Then skip 
	}
	for(;j>=0;--j){
    
		s[j]='*';// When i=-1 when , It means that the number has been copied , Then the front j All become *
	}
}

example 4、 Substring modifier

Given two strings a and b, ask b Whether it is a An anamorphic word of a substring of . For example, the input a=hello,b=lel,lle,ello All are true, however b=elo yes false.
analysis ： Slide window idea
The typical sliding window idea of this problem , Dynamically maintain a window . such as b Is the length of the 3, Then we need to investigate a[0,2],[1,3],[2,4] Whether and b It's an anamorphic word . So how to talk to b Comparison? ？
We use one hash, Based on the particularity of string , It can be used [0,255] perhaps [0,65535] Array of , For the time being, they are all lowercase English letters ,[0,25] To express b The number of occurrences of each word in .
We can save how many non 0 time , It will be useful in the future .

int nonZero = 0;
for(int i=0; i<lenb; i++){
    
	if(++num[b[i]-'a']==1){
    //b[i]-'a' Is to put b The inside number i Bit to 0-25 A number in the middle 
		++nonZero;//nonZero It's statistics num How many numbers in the array are right and wrong 0 Of 
	}
}

We use it b Subtract... From the number of times in a The type of character in a window in the , If the result is all 0, Then find such a substring .
Be careful ：num[] The meaning of becomes the difference of character type

// The first window [0,lenb-1]（ Be careful ：lena<lenb unsolvable ）
for(int i=0; i<lenb; +++i){
    
	int c = a[i] - 'a';
	--num[c];
	if(num[c] == 0){
    
		--nonZero;
	}else if(num[c] == -1){
    
		++nonZero;
	}
}
if(nonZero == 0) return true;

How the window moves ？ Move one bit to the right
New window a[i-lenb+1, i]
Old window a[i-lenb,i-1]
Throw away a[i-lenb], Join in a[i]

for(int i=lenb; i<lena; i++){
    
	int c=a[i-lenb] - 'a';
	++num[c];
	if(num[c]==1) ++nonZero;
	else if(num[c]==0) --nonZero;
	c=a[i]-'a';
	--num[c];
	if(num[c]==0) --nonZero;
	else if(num[c]==-1) ++nonZero;
	if(nonZero==0) return true;
}