算法leetcode

【搜索难题】力扣1258-近义词句子

字数统计: 943字   |   阅读时长: 4分
, , ,

摘要: 力扣 1258，算法大杂烩

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文看一个大杂烩了很多算法的题目。整体的算法并不难，但是涉及到的东西很多。

$1 题目

1258. 近义词句子

给你一个近义词表 synonyms 和一个句子 text ， synonyms 表中是一些近义词对 ，你可以将句子 text 中每个单词用它的近义词来替换。

请你找出所有用近义词替换后的句子，按 字典序排序 后返回。

提示：

1
2
3
4
5
0 <= synonyms.length <= 10
synonyms[i].length == 2
synonyms[0] != synonyms[1]
所有单词仅包含英文字母，且长度最多为 10 。
text 最多包含 10 个单词，且单词间用单个空格分隔开。

示例 1：

输入：
synonyms = [[“happy”,”joy”],[“sad”,”sorrow”],[“joy”,”cheerful”]],
text = “I am happy today but was sad yesterday”
输出：
[“I am cheerful today but was sad yesterday”,
“I am cheerful today but was sorrow yesterday”,
“I am happy today but was sad yesterday”,
“I am happy today but was sorrow yesterday”,
“I am joy today but was sad yesterday”,
“I am joy today but was sorrow yesterday”]

$2 题解

算法: DFS + 哈希表 + 并查集

算法的大框架是搜索，过程中需要哈希表和并查集维护信息。其中哈希表维护词到 id 的映射；并查集维护同义词 id 的集合。

DFS 维护所有拼接成的句子 cand，每次取 text 的一个单词 w：

  • 若 w 在哈希表中没有出现，直接在 cand 后面加 w，继续 DFS。
  • 若 w 在哈希表中出现，查询并查集返回所有同义词 id，将 id 按 words[id] 的字典序排序，对每个 id 都在 cand 插入一次并向后 DFS。

代码 (C++)

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
class UnionFindSet
{
public:
    UnionFindSet(){}
    UnionFindSet(int n)
    {
        _father.assign(n, 0);
        _rank.assign(n, 0);
        syns.assign(n, {});
        for(int i = 0; i < n; ++i)
            _father[i] = i;
        for(int i = 0; i < n; ++i)
            syns[i] = {i};
    }

    void merge(int id1, int id2)
    {
        id1 = _find(id1);
        id2 = _find(id2);
        if(id1 == id2)
            return;

        if(_rank[id1] < _rank[id2])
        {
            _father[id1] = id2;
            syns[id2].insert(syns[id2].end(), syns[id1].begin(), syns[id1].end());
        }
        else
        {
            _father[id2] = id1;
            syns[id1].insert(syns[id1].end(), syns[id2].begin(), syns[id2].end());
            if(_rank[id1] == _rank[id2])
                _rank[id1];
        }
    }

    vector<int> get_syns(int id)
    {
        return syns[_find(id)];
    }

private:
    vector<int> _father;
    vector<int> _rank;
    vector<vector<int>> syns;

    int _find(int id)
    {
        if(_father[id] == id)
            return id;
        return _father[id] = _find(_father[id]);
    }
};

struct Cmp
{
    vector<string> *words;
    Cmp(vector<string>* words):words(words){}
    Cmp(){}
    bool operator()(const int i1, const int i2) const
    {
        return (*words)[i1] < (*words)[i2];
    }
};

class Solution {
public:
    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
        int id = 0;
        words = vector<string>();
        for(vector<string>& record: synonyms)
        {
            if(mapping.count(record[0]) == 0)
            {
                mapping[record[0]] = id++;
                words.emplace_back(record[0]);
            }
            if(mapping.count(record[1]) == 0)
            {
                mapping[record[1]] = id++;
                words.emplace_back(record[1]);
            }
        }
        cmp = Cmp(&words);
        unionfindset = UnionFindSet(id);
        for(vector<string>& record: synonyms)
        {
            unionfindset.merge(mapping[record[0]], mapping[record[1]]);
        }
        vector<string> result;
        string cand;
        dfs(text, 0, cand, result);
        return result;
    }

private:
    unordered_map<string, int> mapping; // word -> id
    vector<string> words;
    UnionFindSet unionfindset;
    Cmp cmp;

    void dfs(const string& text, int pos, string& cand, vector<string>& result)
    {
        int n = text.size();
        if(pos >= n)
        {
            cand.pop_back();
            result.emplace_back(cand);
            cand += ' ';
            return;
        }
        int t = text.find(' ', pos);
        int nxt;
        if(t == -1)
            nxt = n;
        else
            nxt = t;
        string w = text.substr(pos, nxt - pos);
        if(mapping.count(w) == 0)
        {
            cand += w;
            cand += ' ';
            dfs(text, nxt + 1, cand, result);
            cand.pop_back();
            cand.erase(cand.size() - w.size(), w.size());
            return;
        }
        vector<int> syn_ids = unionfindset.get_syns(mapping[w]);
        sort(syn_ids.begin(), syn_ids.end(), cmp);
        for(int id: syn_ids)
        {
            string &syn = words[id];
            cand += syn;
            cand += ' ';
            dfs(text, nxt + 1, cand, result);
            cand.pop_back();
            cand.erase(cand.size() - syn.size(), syn.size());
        }
    }
};
Share