读书笔记 - 字符串匹配
设计模式 - 工厂模式

Leetcode - Index Pairs of a String

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

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.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter