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:
words
are different.1 <= text.length <= 100
1 <= words.length <= 20
1 <= words[i].length <= 50
[i,j]
in sorted order (i.e. sort them by their first coordinate in case of ties sort them by their second coordinate).struct Solution;
use std::collections::HashSet;
use std::iter::FromIterator;
impl Solution {
fn index_pairs(text: String, words: Vec<String>) -> Vec<Vec<i32>> {
let n = text.len();
let mut res: Vec<Vec<i32>> = vec![];
let hs: HashSet<String> = HashSet::from_iter(words);
for i in 0..n {
for j in i..n {
if hs.contains(&text[i..=j]) {
res.push(vec![i as i32, j as i32]);
}
}
}
res
}
}
#[test]
fn test() {
let text = "thestoryofleetcodeandme".to_string();
let words: Vec<String> = vec_string!["story", "fleet", "leetcode"];
let res: Vec<Vec<i32>> = vec_vec_i32![[3, 7], [9, 13], [10, 17]];
assert_eq!(Solution::index_pairs(text, words), res);
let text = "ababa".to_string();
let words: Vec<String> = vec_string!["aba", "ab"];
let res: Vec<Vec<i32>> = vec_vec_i32![[0, 1], [0, 2], [2, 3], [2, 4]];
assert_eq!(Solution::index_pairs(text, words), res);
}