丁丁的博客
0%

字符串题目处理方法

Posted on Edited on In Views: Valine:

最近两天碰到几道字符串题目，总结记录一下通用的方法，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
}