class Solution {
public:
vector<vector<int>> indexPairs(string text, vector<string>& words) {
}
};
1065. 字符串的索引对
给出 字符串 text 和 字符串列表 words, 返回所有的索引对 [i, j] 使得在索引对范围内的子字符串 text[i]...text[j]（包括 i 和 j）属于字符串列表 words。
示例 1:
输入: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"] 输出: [[3,7],[9,13],[10,17]]
示例 2:
输入: text = "ababa", words = ["aba","ab"] 输出: [[0,1],[0,2],[2,3],[2,4]] 解释: 注意，返回的配对可以有交叉，比如，"aba" 既在 [0,2] 中也在 [2,4] 中
提示:
words 中的字符串无重复。1 <= text.length <= 1001 <= words.length <= 201 <= words[i].length <= 50[i,j]（即，按照索引对的第一个索引进行排序，当第一个索引对相同时按照第二个索引对排序）。原站题解
java 解法, 执行用时: 2 ms, 内存消耗: 42.5 MB, 提交时间: 2023-10-15 19:14:52
class Solution {
public int[][] indexPairs(String text, String[] words) {
Stack<int[]> stack = new Stack<int[]>();
MyCmp cmp = new MyCmp();
int n = text.length();
int i = 0;
for (String s : words) {
while (i >= 0 && i < n) {
i = text.indexOf(s, i);
if (i >= 0) {
int[] temp = new int[2];
temp[0] = i;
int sLength = s.length();
int end = i + sLength - 1;
temp[1] = end;
stack.add(temp);
++i;
}
}
i = 0;
}
int size = stack.size();
int[][] res = new int[size][2];
for (int j = size - 1; j >= 0; --j) {
int[] temp = stack.pop();
res[j][0] = temp[0];
res[j][1] = temp[1];
}
Arrays.sort(res, cmp);
return res;
}
private class MyCmp implements Comparator<int[]> {
@Override
public int compare(int[] o1, int[] o2) {
// TODO Auto-generated method stub
int diff = o1[0] - o2[0];
if (diff == 0) {
return o1[1] - o2[1];
}
return diff;
}
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.5 MB, 提交时间: 2023-10-15 19:14:17
func indexPairs1(text string, words []string) [][]int {
n := len(text)
m := map[string]bool{}
m_length := map[int]bool{}
for _, word := range words{
m[word] = true
m_length[len(word)] = true
}
findSub := func(length int)(ret [][]int){
i, j := 0, length
for j <= n{
if m[text[i:j]]{
ret = append(ret, []int{i, j-1})
}
i, j = i+1, j+1
}
return ret
}
ans := [][]int{}
for size := range m_length{
ans = append(ans, findSub(size)...)
}
sort.Slice(ans, func(i, j int)bool{
if ans[i][0] < ans[j][0]{
return true
}
if ans[i][0] == ans[j][0]{
return ans[i][1] < ans[j][1]
}
return false
})
return ans
}
func indexPairs(text string, words []string) (ans[][]int) {
data := []byte(text)
index := suffixarray.New(data)
for _,v:=range words{
sets := index.Lookup([]byte(v), -1)
for _,begin:= range sets{
ans = append(ans,[]int{begin,begin + len(v)-1})
}
}
sort.Slice(ans, func(i, j int) bool {
if ans[i][0]!= ans[j][0]{
return ans[i][0]<ans[j][0]
}
return ans[i][1]<ans[j][1]
})
return
}
python3 解法, 执行用时: 52 ms, 内存消耗: 16.4 MB, 提交时间: 2023-10-15 19:13:30
class Trie:
def __init__(self):
self.child = dict()
self.isWord = False
def insert(self, word: str):
root = self
for c in word:
if c not in root.child:
root.child[c] = Trie()
root = root.child[c]
root.isWord = True
class Solution:
def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
n = len(text)
T = Trie()
for word in words:
T.insert(word)
res = []
for i, c in enumerate(text):
root = T
if c not in root.child:
continue
j = i
while j < n and text[j] in root.child:
root = root.child[text[j]]
if root.isWord == True:
res.append([i, j])
j += 1
return res
python3 解法, 执行用时: 44 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-15 19:13:05
class Solution:
def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
return sorted([[m.start(), m.start()+len(w)-1] for w in words for m in re.finditer('(?={0})'.format(w), text)])
# 自定义排序规则
def indexPairs2(self, text: str, words: List[str]) -> List[List[int]]:
res = []
for one in words:
for i in range(len(text)):
if text[i] == one[0]:
if text[i: i+len(one)] == one:
res.append([i, i+len(one)-1])
def cmp(a, b): # 自定义排序方式
if a[0] == b[0]:
if a[1] >= b[1]: return 1
else: return -1
else:
if a[0] >= b[0]: return 1
else: return -1
import functools
res = sorted(res, key= functools.cmp_to_key(cmp))
return res