[数据结构与算法]剑指offer — 字符串专题

1. 替换空格

• 题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
原题链接

• 思路

  此题比较简单，先准备好一个空串，遍历所给字符串：如果遇到空格就追加%20；遇到正常字符直接追加。

class Solution {
public:
    string replaceSpace(string s) {
        // write code here
        string res;
        for(auto x : s) {
            
            if(x == ' ') res += "%20";
            else res += x;
        }
        return res;
    }
};

2. 字符串的排列

• 题目描述

描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述：
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
原题链接

• 思路

  ps：此题还有一个版本是求数组的全排列，解法相同。

  这道题给的字符串中可能存在重复的字符，要求不重不漏地输出所有组合。为了实现不重复，可以使用 set 存储字符串过滤掉重复数据。但是得到一个重复的字符串是没有意义的，我们应该采取一些办法避免搜索到重复字符串。下面简单介绍一下流程：

  1. 首先按照字典序，对字符串进行排序（这么做是为将重复字符聚集到一起）；
  2. 然后从下标0开始枚举所有字符；
  3. 为了不重复地搜索字符串，规定重复字符的相对顺序保持不变；
  4. 所以每次选择字符摆放位置时，需要判断一下当前字符是否与前一个字符相同，如果相同当前字符就只能在前一个字符后面的位置中挑选；
  5. 当然需要一个 state 记录一下哪些位置已经摆放过了；（bool数组或二进制都可以）

class Solution {
public:
    
    vector<string> res;
    string path;  
    vector<string> Permutation(string str) {
        
        if(str.empty()) return res;
        sort(str.begin(), str.end());
        path.resize(str.size());
        dfs(str, 0, 0, 0);
        sort(res.begin(), res.end());
        return res;
    }
    
    void dfs(string &str, int u, int start, int state) {
        
        if(u == str.size()) {
        
            res.push_back(path);
            return;
        }
        
        if(!u || str[u] != str[u - 1]) start = 0; //位置随便选
        for(int i = start; i < str.size(); i ++)
            if(!(state >> i & 1)) {
                
                path[i] = str[u];
                dfs(str, u + 1, i + 1, state + (1 << i)); //如果是两个相同的值，只能从后面选位置
            }  
    }
};

下面给出一种O(1)的做法，这种做法除了存储结果开辟了空间，其余的操作都是字符串的原地交换。

class Solution {
public:
    
    set<string> res;
    vector<string> Permutation(string str) {
        
        if(str.empty()) return {};  
        dfs(0, str);
        return vector<string>(res.begin(), res.end());
    }
    
    void dfs(int pos, string s) {
        
        if(pos + 1 == s.size()) {
            
            res.insert(s);
            return;
        }
        
        for(int i = pos; i < s.size(); i ++) {
            
            swap(s[pos], s[i]);
            dfs(pos + 1, s);
            swap(s[pos], s[i]);
        }
    }
};

3. 第一个只出现一次的字符

• 题目描述

描述
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
原题链接

• 思路

  开一张哈希表，先遍历字符串记录每个字符出现的次数；
  再从头到尾扫描一遍字符串，找到第一个只出现一次的字符。

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        
        unordered_map<char, int> cnt;
        int res = -1;
        for(auto c : str) cnt[c] ++;
        for(int i = 0; i < str.size(); i ++)
            if(cnt[str[i]] == 1) {
                
                res = i;
                break;
            } 
         return res;
    }
};

由于需要扫描两次字符串，时间复杂度为O(2n)，空间复杂度为O(n)；

我们也可以用位来表示字符出现的次数，C++提供了bitset类，能够节省一定空间。

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        
        // b1表示：某字符至少出现 1 次
        // b2表示：某字符至少出现 2 次
        bitset<128> b1, b2;
        for(auto c : str) 
            if(!b1[c] && !b2[c])
                b1[c] = 1;
            else if (b1[c] && !b2[c])
                b2[c] = 1;
        
        for(int i = 0; i < str.size(); i ++)
            if(b1[str[i]] && !b2[str[i]])
                return i;
        
        return -1;
    }
};

4. 左旋字符串

• 题目描述

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列 S，请你把其循环左移 K 位后的序列输出（保证 K 小于等于 S 的长度）。例如，字符序列S=”abcXYZdef”,要求输出循环左移 3 位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
原题链接

• 思路

  此题要求将字符串的前n个字符移动至末尾，可以分几步解决：

  • 将整个字符串翻转
  • 将字符串的前str.size() - n个字符构成的子串翻转
  • 将字符串的最后n个字符构成的子串翻转

class Solution {
public:
    string LeftRotateString(string str, int n) {
        
        reverse(str.begin(), str.end());
        reverse(str.begin(), str.begin() + str.size() - n);
        reverse(str.begin() + str.size() - n, str.end());
        return str;
    }
};

5. 翻转单词序列

• 题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
原题链接

• 思路

  此题和左旋字符串采用的思路类似，先翻转整个字符串，再利用双指针标记每个单词的起始位置和结束位置。

class Solution {
public:
    string ReverseSentence(string str) { 
        
        reverse(str.begin(), str.end());
        
        for(int i = 0; i < str.size(); i ++) {
            
            int j = i;
            while(j < str.size() && str[j] != ' ') j ++;
            reverse(str.begin() + i, str.begin() + j);
            i = j;
        }
        return str;
    }
};

6. 字符串转换成整数

• 题目描述

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [?231, 231 ? 1]。如果数值超过这个范围，请返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 。
原题链接

• 思路

  这题在leetcode上有环境要求只能存储32位的有符号整数，否则用long long就可以轻松解决；

  此题的难点在于如何在转换整数过程中避免各种越界情况，由于只需要遍历一遍字符串，因此时间复杂度为O(n)。下面给出代码及注释：

class Solution {
public:
    int strToInt(string str) {

        // 忽略行首空格
        int k = 0;
        while(k < str.size() && str[k] == ' ') k ++;
        if(k == str.size()) return 0; //全是空格直返回0
        
        // 判断正负
        int flag = 1;
        if(str[k] == '-') flag = -1, k ++;
        else if(str[k] == '+') k ++;
        
        // 计算整数大小并对越界情况特殊处理
        int res = 0;
        while(k < str.size() && str[k] >= '0' && str[k] <= '9') {

            int x = str[k] - '0';
            if(flag > 0 && res > (INT_MAX - x) / 10) return INT_MAX;
            if(flag < 0 && -res < (INT_MIN + x) / 10) return INT_MIN;
            
            //注意此处比较细节，这里处理了上面两个if解决不了的情形，如下：
            //当flag<0且res*10+x==abs(INT_MIN)时，其中flag<0第一个if进不去，
            //第二个if是严格小于INT_MIN所以也进不去，更难受的是，循环外res*=flag也
            //处理不了，因为abs(INT_MIN)越界。综上，这里加一个特判。
            if(-res * 10 - x == INT_MIN) return INT_MIN; 
            res = res * 10 + x;
            k ++;
        }
        
        res *= flag;
        return res;
    }
};

7. 正则表达式匹配

• 题目描述

请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
原题链接

• 思路

  此题难度较大，算是一道非常经典的DP问题，DP问题的两个关键点是状态建立和状态转移；

  状态表示：f[i][j]表示p从j开始到结尾，是否能匹配s从i开始到结尾;
  状态转移：

  • 如果p[j+1]不是通配符’*’，则f[i][j]是真，当且仅当s[i]可以和p[j]匹配，且f[i+1][j+1]是真；
  • 如果p[j+1]是通配符’*’，则下面的情况只要有一种满足，f[i][j]就是真；
    • f[i][j+2]是真；
    • s[i]可以和p[j]匹配，且f[i+1][j]是真；
  
  

  第1种情况下的状态转移很好理解，那第2种情况下的状态转移怎么理解呢？

  最直观的转移方式是这样的：枚举通配符’*'可以匹配多少个p[j]，只要有一种情况可以匹配，则f[i][j]就是真；
  这样做的话，我们发现，f[i][j]除了枚举0个p[j]之外，其余的枚举操作都包含在f[i+1][j]中了，所以我们只需判断
  f[i+1][j]是否为真，以及s[i]是否可以和p[j]匹配即可。

  时间复杂度分析：n 表示s的长度，m表示p的长度，总共 nm个状态，状态转移复杂度 O(1)，所以总时间复杂度是 O(nm).

  这道题可以用传统的方式写DP，但这里为了使代码更简洁用递归的方式来写，这种方法也叫做记忆化搜索。

class Solution {
public:

    vector<vector<int>> f;
    int n, m;
    string _s, _p;

    bool isMatch(string s, string p) { 

        _s = s, _p = p;
        n = s.size(), m = p.size();
        f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
        return dp(0, 0);
    }

    bool dp(int i, int j) {

        if(f[i][j] != -1) return f[i][j];
        if(j == m) return f[i][j] = i == n;

        bool first_match = i < n && (_s[i] == _p[j] || _p[j] == '.');
        
        bool res;
        if(j + 1 < m && _p[j + 1] == '*')
            res = dp(i, j + 2) || (first_match && dp(i + 1, j));
        else 
            res = first_match && dp(i + 1, j + 1);
        
        return f[i][j] = res;
    }
};

8. 表示数值的字符串

• 题目描述

描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。
原题链接

• 思路

  这道题很考验一个人的思维慎密程度，通常情况下很难一开始就列举出所有非法情形，但是对于此类题目也并非没有入手点，我们可以将非法情况分为几大类，比如：e非法、点非法、+-非法等等。根据这几类情况先写一个初版代码，然后调试代码看看遗漏了哪些情况再进行修改。

class Solution {
public:
    bool isNumber(string s) {

        // 去除行首和行尾空格和最前面的'+/-'
        int i = 0;
        while(i < s.size() && s[i] == ' ') i ++;
        int j = s.size() - 1;
        while(j >= 0 && s[j] == ' ') j --;
        if(i > j) return false;
        s = s.substr(i, j - i + 1);
        if(s[0] == '-' || s[0] == '+') 
            s = s.substr(1);

        // 各种非法情况的讨论
        /*. 1. 全是空格

            2. '+\-'非法
                +、-、+.、-.   
            3. '.'非法
                123e123.4
                12.12.12
            4. e非法
                123e
                e123
                1e1e
                .e1
                e+、e-
            5. 除上面和0~9以外的字符都是非法  
        */
        if(s.empty() || (s[0] == '.' && s.size() == 1)) 
            return false;
        
        int dot = 0, e = 0;
        for(int i = 0; i < s.size(); i ++) {

            if(s[i] >= '0' && s[i] <= '9') ;
            else if(s[i] == '.') {

                dot ++;
                if(e || dot > 1) return false;
            }
            else if(s[i] == 'e' || s[i] == 'E') {
                
                e ++;
                if(i + 1 == s.size() || !i || e > 1 || (s[0] == '.' && i == 1))
                    return false;
                if(s[i + 1] == '+' || s[i + 1] == '-')
                    if(i + 2 == s.size()) return false;
                    else i ++;
            }
            else return false;
        }

        return true;
    }
};

9. 字符流中第一个不重复的字符

• 题目描述

描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
原题链接

• 思路

  此题是对本文中第3题的扩展，第3题给的是定长字符串，而这道题给的是字符流；如果再按照之前的做法，每次插入字符时都需要扫描当前字符串，时间复杂度为O(n^2)。

  显然插入字符前后的两个字符串是有关系的，我们可以维护一个指针始终指向第一个只出现一次的字符，每次插入新字符时更新指针的指向。为了方便写代码，用单调队列来存放当前只出现一次的字符，那么队头作为最先入队的元素一定就是第一个只出现一次的字符。

class Solution{
public:

    unordered_map<char, int> cnt;
    queue<char> q;

    //Insert one char from stringstream
    void insert(char ch){

        if(++ cnt[ch] > 1)
            while(q.size() && cnt[q.front()] > 1) 
                q.pop();
        else q.push(ch);
    }
    //return the first appearence once char in current stringstream
    char firstAppearingOnce(){

        if(q.empty()) return '#';
        else return q.front();
    }
};