【算法】—— 字符串类问题_C

一、基本 *** 作总结

1. substr函数（字符串下标，要截取几个）。PS：字符串下标从0开始

2. substr函数返回的还是string！

3. “==”、“！=”、“>”、“<”可以用作字符串之间的比较，或者字符串和char a[]、字符串和char *a之间的比较。

4. strcmp（）只适用于char a[10]和char a的比较，也就是strcmp只可以比较字符数组

5.得到字符串的长度用length（）函数和size（）函数都可以

二、例题 1. 切割字符串

输入3个字符串，问第三个字符串能否由前两个字符串多次拼接而成。若能，输出前两个字符串分别需要使用几次。若不能则输出FALSE。

1）要考虑到两个子串存在包含的情况，也就是都能与第三个字符串想匹配的情况，解决方法就是总是先匹配长的子串。比如

aa
aab
aabaa :先用aab匹配再用aa，就可以避免先用aa导致后面无法匹配的情况

2）通过这道题发现，如果使用了substr函数，就不用像字符串暴力匹配BF算法一样设置i和j作为子串和主串的指针。

#include
using namespace std;

bool brutal(string &T, string P1, string P2);
int count1=0;
int count2=0;

int main(){
	string T="aabaabaaaab";
	string P1="aa";
	string P2="aab";
	bool flag=false;
	
	//在这里，我们规定让P1的长度大于P2
 	if(P1.length()0){
		flag=brutal(T,P1,P2);
		if(!flag) break;  //两种情况下返回false：①主串T的长度不够了②匹配失败
	}
	
	//输出 
	if(!flag){
		cout<<"false"<

 
 下面给出之前写的一种解题方法，虽然代码更长一些，但是逻辑上更清晰。 
这里要注意的是，substr函数截取的部分超过原字符串长度也没有关系。比如： 
int main(){
	string P1="aa";

	string P3=P1.substr(0,5);  //从P1截取长度为5的字符串，而P1的长度只有2
	cout<
 
# include
using namespace std;

int main(){
    string one;  //子串1
	string two;  //子串2
	string three; //主串
	
	cin>>one;
	cin>>two;
	cin>>three;
	
	int count1=0;
	int count2=0;
	
	int size1=one.length();
	int size2=two.length();
	while(three.length()>=size1||three.length()>=size2){
		if(three.substr(0,size1)==one&&three.substr(0,size2)==two){  //两个小字符串都能匹配时，谁长用谁 
	    	if(size1>=size2)
			{
				three=three.substr(size1,three.length()-size1); 
				count1++; 
			}else
			{
				three=three.substr(size2,three.length()-size2);
				count2++;
			}
		}
		else if(three.substr(0,size1)==one){  //第一个字符串能匹配 
			count1++;
			three=three.substr(size1,three.length()-size1); 
	    		
		}
		else if(three.substr(0,size2)==two){  //第二个能匹配 
			count2++;
			three=three.substr(size2,three.length()-size2);
	    		
		}else //匹配不上了
		{
			break;	
		} 	
	}
	
    //-----------输出--------------
	if(three.length()==0){
		cout<
 
2. 翻转单词 
 
 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。 
 来源：力扣（LeetCode） 
 
  
 
class Solution {
public:
    string reverseWords(string s) {
        /*-----处理空串的特殊情况----*/
        if(s.size()==0) return "";

        string res;
        int n = s.size();
        int right = n - 1;   
        while(right >= 0){
            //从后往前寻找第一字符
            while(right >= 0 && s[right] == ' ') right--;
            if(right < 0) break;

            //从后往前寻找第一个空格
            int left = right;
            while( left >= 0 && s[left] != ' ' ) left--;

            //添加单词到结果
            res += s.substr(left + 1, right - left);
            res += ' ';

            //继续往前分割单词
            right = left;
        }
        //去除最后一个字符空格
        if (!res.empty()) res.pop_back();  //注意判断不空，防止内存溢出
        //或者这样去除最后一个字符空格
        //res=res.substr(0,res.size()-1);
        return res;
    }
}; 
					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/1498315.html

【算法】—— 字符串类问题

发表评论

评论列表（0条）