Leetcode - Index Pairs of a String
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]]
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 | 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)
2 年前
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)].
大约 1 年前
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.