五月集训-02【字符串】

文章目录

• 前言
• 一、练习题目
• 二、思路及题解
• • 1. LC500-键盘行
  • 2. LC1160-拼写单词
  • 3. LC1047-删除字符串中的所有相邻重复项
  • 4. LC1935-可以输入的最大单词数
• 总结

---

前言

        欢迎大家积极在评论区留言一起讨论交流，知无不言，言无不尽，共同进步。本文是 字符串 专题，更多其他专题内容详见《LeetCode每月集训系列》

---

一、练习题目

题目链接	难度	备注
500. 键盘行	★☆☆☆☆
1160. 拼写单词	★☆☆☆☆
1047. 删除字符串中的所有相邻重复项	★☆☆☆☆
1935. 可以输入的最大单词数	★☆☆☆☆

二、思路及题解 1. LC500-键盘行

方法一：哈希表

（1）通过哈希表将同一行字母映射为相同的值；
（2）遍历字符串时（统一将大写字母转化为小写字母）检测不同元素是否为同一哈希值，从而判断是否在同一键盘行；
（3）最后返回满足要求的字符串即可。
代码如下：

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
       vector<string> ans;
       vector<string> query = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
       unordered_map<char, int> hash;

       // 将query映射到哈希表中
       for (int i = 0; i < query.size(); ++i) {
           for (char ch : query[i]) {
               hash[ch] = i;
            }
        }

       for (string word : words) {
           int tmp = -1;
           bool flag = true;
           for (char ch : word) {
               if (tmp == -1) tmp = hash[tolower(ch)];  // 以第一个字符为标准对比
               else if (tmp != hash[tolower(ch)]) {
                   flag = false;
                   break;
               }
            }
            if (flag) ans.push_back(word);
        }
        return ans;
    }
};

2. LC1160-拼写单词

方法一：哈希表

（1）对于一个单词 word，只要其中的每个字母的数量都不大于 chars 中对应的字母的数量，那么就可以用 chars 中的字母拼写出 word。
（2）通过分别两个哈希表便可求解符合要求的 word ，最后返回其长度和即可。

代码如下：

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        unordered_map<char, int> hash;
        int ans = 0;
        for (char ch : chars) {
            ++hash[ch];
        }
        for (string word : words) {
            unordered_map<char, int> word_hash = hash;
            for (char ch : word) {
                    --word_hash[ch]; 
            }
            bool flag = true;
            for (char ch : word) {
                if (word_hash[ch] < 0) {
                    flag = false;
                    break;
                } 
            }
            if (flag) ans += word.size();
        }
        return ans;
    }
};

3. LC1047-删除字符串中的所有相邻重复项

方法一：栈

（1）创建一个字符串来模拟栈的思想，最后作为结果直接输出；
（2）遍历字符串，如果当前字符与栈顶字符相同，则d出；否则，压入当前字符；

代码如下：

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for (char s : S) {
            if(result.empty() || result.back() != s) {
                result.push_back(s);
            } else {
                result.pop_back();
            }
        }
        return result;
    }
};

4. LC1935-可以输入的最大单词数

方法一：哈希表

（1）先创建一个哈希表储存被破坏的键值；
（2）遍历字符串，当遇到空格时表示一个单词已结束，此时根据检查的 flag 状态来进行计数即可；
（3）由于字符串中最后一个单词后无空格，则需在最后再检查一次 flag 的状态。

代码如下：

class Solution {
public:
    int canBeTypedWords(string text, string brokenLetters) {
        int ans = 0;
        unordered_map<char, int> broken_hash;
        for (char ch : brokenLetters) {
            ++broken_hash[ch];
        }
        bool flag = true;
        for (char ch : text) {
            if (ch != ' ') {
                if (broken_hash[ch] != 0) {
                    flag = false;
                } 
            } 
            else {
                if (flag) ++ans;
                else flag = true;
            }
        }
        return flag ? ++ans : ans;
    }
};

---

总结

        题目难不要怕，只要每个月的每一天都坚持刷题学习，总有一天会熟练掌握的。欢迎加入【知识星球｜英雄算法联盟】与我们一同早起刷刷刷⛽️