leetcode字符串题目详解

Leetcode 49. 字母异位词分组

• 此题除了使用哈希或者类似哈希的方式之外，还有一个简单的方式
• 就是将字符串直接按字母排序，相同的就是字母异位词

  class Solution {
  public:
      vector<vector<string>> groupAnagrams(vector<string>& strs) {
          map<string, vector<string>> m;
          for(auto& s : strs)
          {
              string tmp = s;
              sort(tmp.begin(), tmp.end());
              m[tmp].push_back(s);
          }
          vector<vector<string>> ret;
          for(auto& i : m)
          {
              ret.push_back(i.second);
          }
          return ret;
      }
  };

  Leetcode 299. 猜数字游戏

• 遍历两个字符串，假如相同的话就加一个公牛，假如不同的话就对各自的char做数量统计（0, 1, 2, …, 9）各有多少个
• 最终母牛的结果是每个类型的char中谜底和猜测中较小的一个

  class Solution {
  public:
      string getHint(string secret, string guess) {
          int bulls = 0;
          vector<int> cntS(10), cntG(10);
          for (int i = 0; i < secret.length(); ++i) {
              if (secret[i] == guess[i]) {
                  ++bulls;
              } else {
                  ++cntS[secret[i] - '0'];
                  ++cntG[guess[i] - '0'];
              }
          }
          int cows = 0;
          for (int i = 0; i < 10; ++i) {
              cows += min(cntS[i], cntG[i]);
          }
          return to_string(bulls) + "A" + to_string(cows) + "B";
      }
  };

Leetcode 316. 去除重复字母

• 对已经入栈的字符而言，只要后面还出现而且字典顺序大于当前字符的一律弹出，将标记重新设置为0
• 然后加入当前字符，并且设置已经过标记为1
• 意义就是将较大而且后面还出现的字符的出现尽量推迟靠后

  class Solution {
  public:
      string removeDuplicateLetters(string s) {
          vector<int> vis(26), num(26);
          for (char ch : s) {
              num[ch - 'a']++;
          }
  
          string stk;
          // 对已经入栈的字符而言，只要后面还出现而且字典顺序大于当前字符的一律弹出，将标记重新设置为0
          // 然后加入当前字符，并且设置已经过标记为1
          // 意义就是将较大而且后面还出现的字符的出现尽量推迟靠后
          for (char ch : s) {
              if (!vis[ch - 'a']) {
                  while (!stk.empty() && stk.back() > ch) {
                      if (num[stk.back() - 'a'] > 0) {
                          vis[stk.back() - 'a'] = 0;
                          stk.pop_back();
                      } else {
                          break;
                      }
                  }
                  vis[ch - 'a'] = 1;
                  stk.push_back(ch);
              }
              num[ch - 'a'] -= 1;
          }
          return stk;
      }
  };