# Leetcode - Index Pairs of a String

violet posted @ Jun 08, 2020 02:12:28 AM in 读书笔记 with tags Algorithm DFS Trie Golang , 566 阅读

https://leetcode.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]]
```

```type Trie struct {
leaf bool
children []*Trie
}

func indexPairs(text string, words []string) [][]int {
root := &Trie{children: make([]*Trie, 26)}
node := root
for _, w := range words {
node = root
for i := 0; i < len(w); i++ {
index := w[i] - 'a'
if node.children[index] == nil {
node.children[index] = &Trie{children: make([]*Trie, 26)}
}
node = node.children[index]
}
node.leaf = true
}
result := [][]int{}
for i := 0; i < len(text); i++ {
node = root
for j := i; j < len(text); j++ {
index := text[j] - 'a'
if node.children[index] == nil {
break
}
node = node.children[index]
if node.leaf {
result = append(result, []int{i, j})
}
}
}
return result
}```

time complexity: O(n*k)

charlly 说:
Jan 03, 2023 03:46:53 PM

Leetcode is a popular website for practicing coding questions. One question type is to find the index pairs of a given string. This question is particular popular for coding interviews. Theindex pairs of a string are the pairs of indices that correspond to the same character in the string. systemic lupus erythematosus symptoms For example, the string "abab" has the index pairs [(0,3), (1,2)].

datesheet-timetable. 说:
May 02, 2023 07:35:30 PM

Our reporting team intends to publish the Education & Recruitment Update for all age groups and present the true picture of the recent events with the inside coverage. datesheet-timetable.in Our objective would be to cater the requirements of people of all age groups as we intend to publish news. Our team comprises of professional writers & citizen journalists with diverse range of interest in Journalism who are passionate about publishing the Education Updates with transparency in general public interest.

(输入验证码)
or Ctrl+Enter