LeetCode-string类总结（会持续更新...）

本文主要是对leetcode中的string类算法的总结，包含了各题的solution和常用的解决方法。

相关源码：code

125. Valid Palindrome

Description:

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

解题思路：本题判读回文，看到回文我们通常会直接想到使用栈 ，代码如下：

class Solution {
public:
    bool isPalindrome(string s) {
        stack<char> bag;
        string str = "";
        for(int i=0;i<s.size();i++){
            if(s[i]>='A' && s[i]<='Z'){
                str += char(s[i]+32);
                bag.push(s[i]+32);
            }else if((s[i]>='a'&&s[i]<='z')||(s[i]>='0'&&s[i]<='9')){
                str += s[i];
                bag.push(s[i]);
            }
        }
        int len = bag.size();
        //if(len==1 && s.size()>1) return false;
        int count = 0;
        for(int i=0;i<len;i++){
            if(str[i] != bag.top()) break;
            count++;
            bag.pop();
        }
        return count==len;
    }
};

168. Excel Sheet Column Title

Description:

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 

解题思路：本题考察进制，需要注意的一点是：此题中不是从0才是，而是从1开始。代码如下：

class Solution {
public:
    string convertToTitle(int n) {
        string s="";
        if(n<27){
            s+=char(64+n);
            return s;
        }
        int x = n%26;
        n /= 26;
        if(x == 0){
            n--;
            x=26;
        }
        s = convertToTitle(n) + char(64+x);
        return s;
    }
};

459. Repeated Substring Pattern

Description:

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"

Output: True

Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"

Output: False

Example 3:

Input: "abcabcabcabc"

Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

解题思路：本题判断字符串是否是由重复子串组成的，这题有个trick：将原始串扩增一倍，去掉首尾各一个字符，判断此串是否含有原始串，代码如下：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        if(s.size() < 2) return false;
        string temp = s+s;
        temp = temp.substr(1,temp.size()-2);
        return temp.find(s)!=-1;
    }
};

606. Construct String from Binary Tree

Description:

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

Output: "1(2(4))(3)"

Explanation: Originallay it needs to be "1(2(4)())(3()())", 
but you need to omit all the unnecessary empty parenthesis pairs. 
And it will be "1(2(4))(3)".

Example 2:

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example, 
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

解题思路：本题涉及到了树，我们首先确定树的遍历方式，本题适合前序遍历，代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* t) {
      if(t == NULL) return "";
      string result = "";
      result += to_string(t->val);
      string left = tree2str(t->left);
      string right = tree2str(t->right);
      
      if(left=="" && right=="") return result;
      if(left=="") return result+"()"+"("+right+")";
      if(right=="") return result+"("+right+")";
      
      return result+"("+left+")"+"("+right+")";
    }
};

557. Reverse Words in a String III

Description:Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

解题思路：本题要求反转字符串，很自然的会想到用栈 ，但是本题提示不能使用额外的空间，那只能STL中的方法reverse(), 代码如下：

class Solution {
public:
    string reverseWords(string s) {
        for (int i = 0; i < s.length(); i++) {
            if (s[i] != ' ') {   // when i is a non-space
                int j = i;
                for (; j < s.length() && s[j] != ' '; j++) { } // move j to the next space
                reverse(s.begin() + i, s.begin() + j);
                i = j - 1;
            }
        }
        
        return s;
    }
};

520. Detect Capital

Description:

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

1. All letters in this word are capitals, like “USA”.
2. All letters in this word are not capitals, like “leetcode”.
3. Only the first letter in this word is capital if it has more than one letter, like “Google”.

Example 1:

Input: "USA"
Output: True

Example 2:

Input: "FlaG"
Output: False

Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.

代码如下：

class Solution {
public:
    bool detectCapitalUse(string word) {
        int count = 0;
        for(int i=0; i<word.size(); i++){
            if(word[i]<97) count++;
        }
        if(count==word.size() || count==0){
            return true;
        }else if(count==1){
            return word[0] < 97;
        }
        return false;
    }
};

392. Is Subsequence

Description:

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and sis a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

解题思路：代码如下：

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.size()==0) return true;
        int indexT=0, indexS=0;
        while(indexT<t.size()){
            if(t[indexT]==s[indexS]){
                indexS++;
                if(indexS==s.size()) return true;
            }
            indexT++;
        }
        return false;
    }
};