题目地址：https://leetcode-cn.com/problems/index-pairs-of-a-string/
题目描述
Given a text string and words (a list of strings), return all index pairs [i, j] so that the substring text[i]...text[j] is in the list of words.
Example 1:
Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]
Example 2:
Input: text = "ababa", words = ["aba","ab"]
Output: [[0,1],[0,2],[2,3],[2,4]]
Explanation:
Notice that matches can overlap, see "aba" is found in [0,2] and [2,4].
Note:
1、 AllstringscontainsonlylowercaseEnglishletters.；
2、 It'sguaranteedthatallstringsinwordsaredifferent.；
3、 1<=text.length<=100；
4、 1<=words.length<=20；
5、 1<=words[i].length<=50Returnthepairs[i,j]insortedorder(i.e.sortthembytheirfirstcoordinateincaseoftiessortthembytheirsecondcoordinate).；
题目大意
给出字符串 text 和 字符串列表 words, 返回所有的索引对 [i, j] 使得在索引对范围内的子字符串 text[i]...text[j]（包括 i 和 j）属于字符串列表 words。
解题方法
遍历
暴力遍历所有的字符串子串，看其是否在words中。为了加速查找效率，使用的set。
C++代码如下：
class Solution {
public:
vector<vector<int>> indexPairs(string text, vector<string>& words) {
unordered_set<string> wordset(words.begin(), words.end());
const int N = text.size();
vector<vector<int>> res;
for (int i = 0; i < N; ++i) {
for (int j = i; j < N; ++j) {
string cur = text.substr(i, j - i + 1);
if (wordset.count(cur)) {
res.push_back({i, j});
}
}
}
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发