最新消息: USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。

2022.1.9 力扣

IT圈 admin 3浏览 0评论

2022.1.9 力扣

哭了,经典卡在第三题一个小时,看了题解后真想给自己来一巴掌

题目描述:

给你两个下标从 0 开始的字符串数组 startWords 和 targetWords 。每个字符串都仅由 小写英文字母 组成。

对于 targetWords 中的每个字符串,检查是否能够从 startWords 中选出一个字符串,执行一次 转换操作 ,得到的结果与当前 targetWords 字符串相等。

转换操作 如下面两步所述:

追加 任何 不存在 于当前字符串的任一小写字母到当前字符串的末尾。
例如,如果字符串为 "abc" ,那么字母 'd'、'e' 或 'y' 都可以加到该字符串末尾,但 'a' 就不行。如果追加的是 'd' ,那么结果字符串为 "abcd" 。
重排 新字符串中的字母,可以按 任意 顺序重新排布字母。
例如,"abcd" 可以重排为 "acbd"、"bacd"、"cbda",以此类推。注意,它也可以重排为 "abcd" 自身。
找出 targetWords 中有多少字符串能够由 startWords 中的 任一 字符串执行上述转换操作获得。返回 targetWords 中这类 字符串的数目 。

注意:你仅能验证 targetWords 中的字符串是否可以由 startWords 中的某个字符串经执行操作获得。startWords 中的字符串在这一过程中 不 发生实际变更。

样例:

方法一(位运算):

class Solution {
public:int wordCount(vector<string>& startWords, vector<string>& targetWords) {set<int> sets;for (string str : startWords){int x = 0;for (char ch : str){x ^= 1 << (ch - 'a');}sets.insert(x);}int ans = 0;for (string str : targetWords){int x = 0;for (char ch : str){x ^= 1 << (ch - 'a');}for (char ch : str){int temp = x;temp ^= 1 << (ch - 'a');if (sets.count(temp)){ans++;break;}}}return ans;}
};

这个方法挺巧妙的,由于各个单词中的字母出现次数是不重复的,所以可以利用异或将每个单词转换为一个对应的二进制数,然后再将targetWords中的每个单词枚举去掉某个字母后得到的单词的二进制数,是否存在于由starWords所算出来的二进制数集合中。

方法二(哈希表)

class Solution {
public:int wordCount(vector<string>& startWords, vector<string>& targetWords) {unordered_set<string> sets;for (string str : startWords){sort(str.begin(), str.end());int hash[26] = {0};for (char ch : str){hash[ch - 'a'] = 1;}for (char ch = 'a'; ch <= 'z'; ch++){if (hash[ch - 'a'] == 0){string temp = str + ch;sort(temp.begin(), temp.end());sets.insert(temp);}}}int ans = 0;for (string str : targetWords){sort(str.begin(), str.end());if (sets.count(str)){ans++;}}return ans;}
};

就是这个方法,看得我真想给自己来一巴掌,写题时一直想着如果用排序的话,复杂度就是n * nlogn,将会超时,但是实际上是n * slogs(s为字符串的长度,最大为26),是符合时间要求的!

今天写的实在有点郁闷,第二题都比第三题难反而写出来了,字符串题目还是得多练练,每次遇到难点的字符串的题目都得卡半天,而且还有不少小技巧,例如方法一中将单词转换为二进制数的方法,如果知道这一技巧的话这道题将会更加简单。

2022.1.9 力扣

哭了,经典卡在第三题一个小时,看了题解后真想给自己来一巴掌

题目描述:

给你两个下标从 0 开始的字符串数组 startWords 和 targetWords 。每个字符串都仅由 小写英文字母 组成。

对于 targetWords 中的每个字符串,检查是否能够从 startWords 中选出一个字符串,执行一次 转换操作 ,得到的结果与当前 targetWords 字符串相等。

转换操作 如下面两步所述:

追加 任何 不存在 于当前字符串的任一小写字母到当前字符串的末尾。
例如,如果字符串为 "abc" ,那么字母 'd'、'e' 或 'y' 都可以加到该字符串末尾,但 'a' 就不行。如果追加的是 'd' ,那么结果字符串为 "abcd" 。
重排 新字符串中的字母,可以按 任意 顺序重新排布字母。
例如,"abcd" 可以重排为 "acbd"、"bacd"、"cbda",以此类推。注意,它也可以重排为 "abcd" 自身。
找出 targetWords 中有多少字符串能够由 startWords 中的 任一 字符串执行上述转换操作获得。返回 targetWords 中这类 字符串的数目 。

注意:你仅能验证 targetWords 中的字符串是否可以由 startWords 中的某个字符串经执行操作获得。startWords 中的字符串在这一过程中 不 发生实际变更。

样例:

方法一(位运算):

class Solution {
public:int wordCount(vector<string>& startWords, vector<string>& targetWords) {set<int> sets;for (string str : startWords){int x = 0;for (char ch : str){x ^= 1 << (ch - 'a');}sets.insert(x);}int ans = 0;for (string str : targetWords){int x = 0;for (char ch : str){x ^= 1 << (ch - 'a');}for (char ch : str){int temp = x;temp ^= 1 << (ch - 'a');if (sets.count(temp)){ans++;break;}}}return ans;}
};

这个方法挺巧妙的,由于各个单词中的字母出现次数是不重复的,所以可以利用异或将每个单词转换为一个对应的二进制数,然后再将targetWords中的每个单词枚举去掉某个字母后得到的单词的二进制数,是否存在于由starWords所算出来的二进制数集合中。

方法二(哈希表)

class Solution {
public:int wordCount(vector<string>& startWords, vector<string>& targetWords) {unordered_set<string> sets;for (string str : startWords){sort(str.begin(), str.end());int hash[26] = {0};for (char ch : str){hash[ch - 'a'] = 1;}for (char ch = 'a'; ch <= 'z'; ch++){if (hash[ch - 'a'] == 0){string temp = str + ch;sort(temp.begin(), temp.end());sets.insert(temp);}}}int ans = 0;for (string str : targetWords){sort(str.begin(), str.end());if (sets.count(str)){ans++;}}return ans;}
};

就是这个方法,看得我真想给自己来一巴掌,写题时一直想着如果用排序的话,复杂度就是n * nlogn,将会超时,但是实际上是n * slogs(s为字符串的长度,最大为26),是符合时间要求的!

今天写的实在有点郁闷,第二题都比第三题难反而写出来了,字符串题目还是得多练练,每次遇到难点的字符串的题目都得卡半天,而且还有不少小技巧,例如方法一中将单词转换为二进制数的方法,如果知道这一技巧的话这道题将会更加简单。

与本文相关的文章

发布评论

评论列表 (0)

  1. 暂无评论