字符串常用函数汇总

下述函数使用之前，都要包含头文件#include < string >。 假设初始字符串为: string str.

• getline(): 读入一个字符串，可读取整行，包括前导和嵌入的空格，并将其存储在字符串对象中。 为什么不能无脑cin：当cin读取数据时，它会传递并忽略任何前导白色空格字符（空格、制表符或换行符）。一旦它接触到第一个非空格字符即开始阅读，当它读取到下一个空白字符时，它将停止读取。这就意味着cin无法读取一整个句子，如”Billy Xie is right here.”，因为上句出现了空格。
• string a = to_string(num): 将数字常量num转换为字符串，返回值为转换完毕的字符串a. 常用于数字常量需和字符串一起打印的场合。
• str.substr(a, b): 复制子字符串，从指定位置a开始，截取长度为b的字符串.
• int b = stoi(): 将数字字符转化为int输出，string to int嘛。需要注意的是，stoi()会对参数字符串进行范围判断，默认范围是在int的范围内[ -2147483648, 2147483647]的，如果超出范围的话则会runtime error.
• isalpha(str) ：判断字符str是否为英文字母，若为英文字母，返回非0（小写字母为2，大写字母为1）。若不是字母，返回0。

int main()
{

    string str = "111111";
    int b = stoi(str);
    cout << a << endl;//输出111111
    return 0;
}    

LC第5题：最长回文子串

给定一个字符串s，找到s中最长的回文子串。

解题思路1：双指针

首先确定回文串，就是找中心然后想两边扩散看是不是对称的。在遍历中心点的时候，要注意中心点有两种情况：一个元素可以作为中心点，两个元素也可以作为中心点。这两种情况可以涵盖回文的所有情况。分别以i为中心和以i & i+1为中心计算进行计算，代码如下：

代码示例

int left = 0;
int right = 0;
int maxLength = 0;
string longestPalindrome(string s) {
    int result = 0;
    for (int i = 0; i < s.size(); i++) {
        extend(s, i, i, s.size()); // 以i为中心
        extend(s, i, i + 1, s.size()); // 以i和i+1为中心
    }
    return s.substr(left, maxLength);
}
//定义extend函数，用于寻找范围内的回文子串
void extend(const string& s, int i, int j, int n) {
    while (i >= 0 && j < n && s[i] == s[j]) {
        if (j - i + 1 > maxLength) {
            left = i;
            right = j;
            maxLength = j - i + 1;
        }
        i--;
        j++;
    }
}

解题思路2：动态规划

代码如下

string longestPalindrome(string s) {
    int n = s.size();
    if (n < 2) {
        return s;
    }

    int maxLen = 1;
    int begin = 0;
    // dp[i][j] 表示 s[i..j] 是否是回文串
    vector<vector<int>> dp(n, vector<int>(n));
    // 初始化：所有长度为 1 的子串都是回文串
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    // 递推开始
    // 先枚举子串长度
    for (int L = 2; L <= n; L++) {
        // 枚举左边界，左边界的上限设置可以宽松一些
        for (int i = 0; i < n; i++) {
            // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
            int j = L + i - 1;
            // 如果右边界越界，就可以退出当前循环
            if (j >= n) {
                break;
            }

            if (s[i] != s[j]) {
                dp[i][j] = false;
            } else {
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }

            // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                begin = i;
            }
        }
    }
    return s.substr(begin, maxLen);
}

LC第14题：最长公共前缀

如果不存在公共前缀，返回空字符串 ““。

解题思路

纵向遍历，把字符串看成字符串数组，每个字符串为一行，一共有整数行。先横向遍历第一个字符串，之后将下面的每个字符串都和它对比。如果发现第一个不同的字符，就返回第一个~前一个字符。

代码示例

string longestCommonPrefix(vector<string>& strs) {
    if(!strs) return "";
    int length = strs[0].length();
    int count = strs.size();
    for(int i = 0; i < length; i++) {
        char c = strs[0][i];
        for(int j = 1; j < count; j++) {
            if(strs[0].size() == i || strs[j][i] != c) {
                return strs[0].substr(0, i);
            }
        }
    }
    return strs[0];
}

LC第387题：字符串中的第一个唯一字符

给定一个字符串 s ，找到它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。 这里只需要考虑小写字母。

解题思路1

使用一个数组来记录出现过的小写字母。如果出现i次，就记录为index[s[i] - ‘a’]。然后再遍历一次数组，找i=1的即可。

代码示例1

int firstUniqChar(string s) {
    int a[26]={0};
    int index[26];
    int size=s.size();
    for(int i=0;i<size;i++) {
        a[s[i]-'a']++;
        index[s[i]-'a']=i;
    }
    for(int i=0;i<size;i++) {
        if(a[s[i]-'a']==1) {
            return index[s[i]-'a'];
        }
    }
    return -1;
}    

解题思路2

直接使用哈希表存储每个字符出现的频次，之后进行二次遍历。只要其中一个字符串的value值为1，就马上返回这个元素下标。

代码示例2

int firstUniqChar(string s) {
    unordered_map<char, int> pairs;
    for(int i = 0 ; i < s.length(); i++) {
        pairs[s[i]]++;//使用哈希表存储每个字符出现的频次
    }
    for(int i = 0 ; i < s.length(); i++) {
        if(pairs[s[i]] == 1) {
            return i;
        }
    }
    return -1;
}

LC第242题：有效的字母异位词

给定两个字符串s,t，判断t是否为s的字母异位词，即每个字母出现的频次都相同。本题默认没有数字。

解题思路1

解题思路和上一道题大同小异。用一个数组a[26]存储所有出现的字母及其频次，然后a[t[i] - ‘a’]–，使用t的字母及频次对数组a进行“抵消”。如果最终结果为0，则返回true。

代码示例1

bool isAnagram(string s, string t) {
    int shash[26] = {0};
    int thash[26] = {0};
    for(int i=0;i<s.size();i++) {
        shash[s[i]-'a']++;
    }
    for(int i=0;i<t.size();i++) {
        thash[t[i]-'a']++;
    }
    for(int i=0;i<26;i++) {
        if(shash[i] != thash[i]) {
            return false;
        }
    }
    return true;
}

• 代码疑惑

在第三个for语句判断中，为什么判断不等，返回false就可以过，而判断相等,返回true就过不了呢…

• 问题解答

这是因为，每个字符出现的次数都需要相等才能判断true，而单次判断true肯定不能确定是字母异位词，因此需要判断不等。

解题思路2

第二个思路和上一题的第二个思路基本类似。直接使用哈希表存储第一个字符串每个字符出现的频次，之后进行二次遍历，对出现的频次进行递减。只要其中一个字符串的value值不为0，就马上返回false。反之就是全部对应完成，输出true。

代码示例2

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> pairs1;
        if(s.length() != t.length()) return false;
        for(int i = 0; i < s.length(); i++) {
            pairs1[s[i]]++;
        }
        for(int i = 0; i < t.length(); i++) {
            pairs1[t[i]]--;
        }
        for(int i = 0; i < t.length(); i++) {
            if(pairs1[s[i]] != 0) {
                return false;
            }
        }        
        return true;
    }
};

• Previous
  螺旋矩阵
• Next
  C++11新特性