最近两天碰到几道字符串题目,总结记录一下通用的方法,C++要自己写切片函数搞字符串还是有点麻烦,python或者go会更方便一点。
切片函数 一般按空格划分,当碰到类似于单词匹配时可以用来存储每个单词子串,再借助哈希表来求解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 vector<string> split (string &str ,char target){ vector<string> res string s(str ) int pos = 0 while (pos < s.size()){ while (pos < s.size() && s[pos ] == target){ pos ++ } int start = pos while (pos < s.size() && s[pos ] != target) { pos ++ } if (pos > start){ res.emplace_back(s.substr(start,pos - start)) } } return res }
例题: Leetcode.1813 句子相似性Ⅲ 一个句子是由一些单词与它们之间的单个空格组成,且句子的开头和结尾没有多余空格。比方说,”Hello World”,”HELLO”,”hello world hello world”都是句子。每个单词都只包含大写和小写英文字母。 如果两个句子sentence1和sentence2,可以通过往其中一个句子插入一个任意的句子(可以是空句子)而得到另一个句子,那么我们称这两个句子是相似的 。比方说,sentence1 = “Hello my name is Jane” 且 sentence2 = “Hello Jane” ,我们可以往sentence2中 “Hello”和”Jane”之间插入”my name is”得到sentence1。 给你两个句子sentence1和sentence2,如果sentence1和sentence2是相似的,请你返回true,否则返回false。https://leetcode.cn/problems/sentence-similarity-iii/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution {public : vector<string_view> split (const string &str,char target) { vector<string_view> res; string_view s (str) ; int pos = 0 ; while (pos < s.size ()){ while (pos < s.size () && s[pos] == target){ pos++; } int start = pos; while (pos < s.size () && s[pos] != target) { pos++; } if (pos > start){ res.emplace_back (s.substr (start,pos - start)); } } return res; } bool areSentencesSimilar (string sentence1, string sentence2) { vector<string_view> s1 = split (sentence1,' ' ); vector<string_view> s2 = split (sentence2,' ' ); for (int i = 0 ;i < s1.size ();i++){ cout<<s1[i]<<" " ; } cout<<endl; for (int i = 0 ;i < s2.size ();i++){ cout<<s2[i]<<" " ; } int i = 0 ,j = 0 ; while (i < s1.size () && i < s2.size () && s1[i] == s2[i]){ i++; } while (j < s1.size () - i && j < s2.size () - i && s1[s1.size () - j - 1 ] == s2[s2.size () - j - 1 ]){ j++; } cout<<i<<" " <<j; return i + j == min (s1.size (),s2.size ()); } };
Leetcode.2512 奖励最顶尖的 K 名学生 出自leetcode第94场双周赛 给你两个字符串数组positive_feedback和negative_feedback,分别包含表示正面的和负面的词汇。不会有单词同时是正面的和负面的。 一开始,每位学生分数为0.每个正面的单词会给学生的分数加3分,每个负面的词会给学生的分数减1分。 给你n个学生的评语,用一个下标从0开始的字符串数组report和一个下标从0开始的整数数组student_id表示,其中student_id[i]表示这名学生的ID,这名学生的评语是report[i]。每名学生的ID互不相同。 给你一个整数k,请你返回按照得分从高到低最顶尖的k名学生。如果有多名学生分数相同,ID越小排名越前。https://leetcode.cn/problems/reward-top-k-students/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution {public : vector<string> split (string &str,char target) { vector<string> res; string s (str) ; int pos = 0 ; while (pos < s.size ()){ while (pos < s.size () && s[pos] == target){ pos++; } int start = pos; while (pos < s.size () && s[pos] != target){ pos++; } if (pos > start){ res.emplace_back (s.substr (start,pos - start)); } } return res; } vector<int > topStudents (vector<string>& positive_feedback, vector<string>& negative_feedback, vector<string>& report, vector<int >& student_id, int k) { unordered_set<string> cnt1; unordered_set<string> cnt2; int n = report.size (); unordered_map<int ,int > hash; for (int i = 0 ;i < positive_feedback.size ();i++)cnt1.insert (positive_feedback[i]); for (int i = 0 ;i < negative_feedback.size ();i++)cnt2.insert (negative_feedback[i]); for (int i = 0 ;i < n;i++){ vector<string> s = split (report[i],' ' ); for (int j = 0 ;j < s.size ();j++){ if (cnt1.count (s[j]))hash[student_id[i]] += 3 ; if (cnt2.count (s[j]))hash[student_id[i]] -= 1 ; } } sort (student_id.begin (),student_id.end (),[&](int a,int b){ if (hash[a] == hash[b])return a < b; return hash[a] > hash[b]; }); vector<int > ans; for (int i = 0 ;i < k;i++)ans.push_back (student_id[i]); return ans; } };
Go语言自带切片函数,用起来要方便很多。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 func topStudents (positive_feedback []string , negative_feedback []string , report []string , student_id []int , k int ) []int { score := map [string ]int {} for _,w := range positive_feedback{ score[w] = 3 } for _,w := range negative_feedback{ score[w] = -1 } type pair struct {score,id int } a := make ([]pair,len (report)) for i,r := range report{ s := 0 for _, w := range strings.Split(r, " " ) { s += score[w] } a[i] = pair{s,student_id[i]} } sort.Slice(a, func (i, j int ) bool { a, b := a[i], a[j] return a.score > b.score || a.score == b.score && a.id < b.id }) ans := make ([]int , k) for i, p := range a[:k] { ans[i] = p.id } return ans }