字符串问题(上)

一、 字符串变形

解法一:双逆转(推荐)

将单词位置的反转，那肯定前后都是逆序，不如我们先将整个字符串反转，这样是不是单词的位置也就随之反转了。但是单词里面的成分也反转了啊，既然如此我们再将单词里面的部分反转过来就行。

• 遍历字符串，遇到小写字母，转换成大写，遇到大写字母，转换成小写，遇到空格正常不变。
• 第一次反转整个字符串，这样基本的单词逆序就有了，但是每个单词的字符也是逆的。
• 再次遍历字符串，以每个空间为界，将每个单词反转回正常。

class Solution {
    
public:
    string trans(string s, int n) {
    
        // write code here
        if(n==0)
            return s;
        string res;
        for(int i=0;i<n;i++)
        {
    
            if(isupper(s[i]))
                res+=tolower(s[i]);
            else if(islower(s[i]))
                res+=toupper(s[i]);
            else
                res+=s[i];
        }
        reverse(res.begin(),res.end());
        for(int i=0;i<n;i++)
        {
    
            int j=i;
            while(j<n&&res[j]!=' ')
                j++;
            reverse(res.begin()+i,res.begin()+j);
            i=j;
        }
        return res;
    }
};

时间复杂度：O(n)，虽有多个循环，但是每个循环都只有一层O(n)
空间复杂度：O(n)，res是存储变换的临时字符串，也可以直接用s直接变换，这样就为O(1)

解法二:分割字符串+栈

题目要求将单词逆序，逆序我们就可以想到先进后出的栈，单词之间分开逆序我们需要整个字符串分割。

• 遍历字符串，遇到小写字母，转换成大写，遇到大写字母，转换成小写，遇到空格正常不变。
• 按照空格把字符串分割成一个个单词.
• 遍历分割好的单词，将单词依次存入栈中。
• 再从栈中弹出单词，拼接成字符串。

class Solution {
    
public:
    string trans(string s, int n) {
    
        // write code here
        if(!n)
            return s;
        string res;
        for(int i=0;i<n;i++)
        {
    
            if(isupper(s[i]))
                res+=tolower(s[i]);
            else if(islower(s[i]))
                res+=toupper(s[i]);
            else
                res+=s[i];
        }
        stack<string>tmp;
        for(int i=0;i<n;i++)
        {
    
            int j=i;
            while(j<n&&res[j]!=' ')
                j++;
            tmp.push(res.substr(i,j-i));
            i=j;
        }
        if(s[n-1]==' ')
            res=" ";
        else
            res="";
        while(!tmp.empty())
        {
    
            res+=tmp.top();
            tmp.pop();
            if(!tmp.empty())
                res+=" ";
        }
        return res;
    }
};

时间复杂度：O(n)，所有循环最多遍历一次
空间复杂度：O(n)，栈空间的大小最坏为O(n)

二、最长公共前缀

解法一:子串纵向查找

既然是公共前缀，那我们可以用一个字符串与其他字符串进行比较，从第一个字符开始，逐位比较，找到最长公共子串。

• 处理数组为空的特殊情况。
• 因为最长公共前缀的长度不会超过任何一个字符串的长度，因此我们逐位就以第一个字符串为标杆，遍历第一个字符串的所有位置，取出字符。
• 遍历数组中后续字符串，依次比较其他字符串中相应位置是否为刚刚取出的字符，如果是，循环继续，继续查找，如果不是或者长度不足，说明从第i位开始不同，前面的都是公共前缀。
• 如果遍历结束都相同，最长公共前缀最多为第一个字符串。

class Solution {
    
public:

    string longestCommonPrefix(vector<string>& strs) {
    
        // write code here
        if(!strs.size())return "";//特判若子串为空则返回空值
        for(int i=0;i<strs[0].size();i++){
    //枚举第一个子串的每个字符
            for(int j=1;j<strs.size();j++){
    //枚举后面所有子串
                if(strs[0][i]!=strs[j][i]||i==strs[j].size()){
    //比较后面所有子串的第i列字符和第j个子串的长度
                    return strs[0].substr(0,i);//若字符不相同或者长度为最小则返回最长公共前缀
                }
            }
        }
        return strs[0];
    }
};

时间复杂度：O(mn)，其中n 是字符串的数量，m 是字符串数组中的字符串的平均长度。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)。额外空间复杂度为常数。

解法二:排序后子串纵向查找

先将所以子字符串按照字典序的大小排序，想要得到最长公共前缀，只需要将字典序最小的子串A与字典序最大的B比较相同部分，得到的最长公共前缀就是所有子串的公共前缀。

class Solution {
    
public:

    string longestCommonPrefix(vector<string>& strs) {
    
         if(!strs.size())return "";
         sort(strs.begin(),strs.end());//按照字典序排序得到所有子串顺序
         string a=strs.front(),b=strs.back();//枚举第一个最小的子串和最后一个最大的子串
         int i=0;
         for(i=0;i<a.size()&&a[i]==b[i];i++);//若字符相同则继续比较否则返回最长公共前缀串
         return a.substr(0,i);

    }
};

时间复杂度：O(n${\log }_2$n)，其中n 是字符串的数量，排序算法时间复杂度O(n${\log }_2$n).
空间复杂度：O(1)。额外空间复杂度为常数。