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]]

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)

• 相关文章
• 全局相关文章