String Problem (Part 1)

一、 字符串变形

解法一:双逆转(推荐)

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

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

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),Although there are multiple loops,But each loop has only one layerO(n)
空间复杂度：O(n),resis a temporary string where the transformation is stored,也可以直接用s直接变换,这样就为O(1)

解法二:分割字符串+栈

The question asks to reverse the order of the words,In reverse order, we can think of a first-in-last-out stack,To split between words in reverse order we need to split the whole string.

• 遍历字符串,遇到小写字母,转换成大写,遇到大写字母,转换成小写,遇到空格正常不变.
• Split the string into words by spaces.
• Traverse the segmented words,Put the words on the stack one by one.
• Then pop the word from the stack,拼接成字符串.

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),All loops are traversed at most once
空间复杂度：O(n),The worst size of the stack space is O(n)

二、最长公共前缀

解法一:Substring search vertically

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

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

class Solution {
    
public:

    string longestCommonPrefix(vector<string>& strs) {
    
        // write code here
        if(!strs.size())return "";//In particular, if the substring is empty, it returns a null value
        for(int i=0;i<strs[0].size();i++){
    //Enumerates each character of the first substring
            for(int j=1;j<strs.size();j++){
    //Enumerates all subsequent substrings
                if(strs[0][i]!=strs[j][i]||i==strs[j].size()){
    //Compare the first of all subsequent substringsicolumn characters andjlength of the substring
                    return strs[0].substr(0,i);//Returns the longest common prefix if the characters are not the same or the length is the smallest
                }
            }
        }
        return strs[0];
    }
};

时间复杂度：O(mn),其中n 是字符串的数量,m 是字符串数组中的字符串的平均长度.最坏情况下,字符串数组中的每个字符串的每个字符都会被比较一次.
空间复杂度：O(1).The additional space complexity is constant.

解法二:After sorting, the substring is searched vertically

First sort all substrings according to their lexicographical size,Want to get the longest common prefix,Only the lexicographically smallest substring is requiredAwith the lexicographical largestBCompare the same parts,The resulting longest common prefix is ​​the common prefix of all substrings.

class Solution {
    
public:

    string longestCommonPrefix(vector<string>& strs) {
    
         if(!strs.size())return "";
         sort(strs.begin(),strs.end());//All substrings are sorted lexicographically
         string a=strs.front(),b=strs.back();//Enumerates the first smallest substring and the last largest substring
         int i=0;
         for(i=0;i<a.size()&&a[i]==b[i];i++);//If the characters are the same, continue to compare otherwise return the longest common prefix string
         return a.substr(0,i);

    }
};

时间复杂度：O(n${\log }_2$n),其中n 是字符串的数量,排序算法时间复杂度O(n${\log }_2$n).
空间复杂度：O(1).The additional space complexity is constant.