Trie
Array
String
Sorting
Description
Given a string text
and an array of strings words
, return an array of all index pairs [i, j]
so that the substring text[i...j]
is in words
.
Return the pairs [i, j]
in sorted order (i.e., sort them by their first coordinate, and in case of ties sort them by their second coordinate).
Example 1:
Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]
Example 2:
Input: text = "ababa", words = ["aba","ab"]
Output: [[0,1],[0,2],[2,3],[2,4]]
Explanation: Notice that matches can overlap, see "aba" is found in [0,2] and [2,4].
Constraints:
1 <= text.length <= 100
1 <= words.length <= 20
1 <= words[i].length <= 50
text
and words[i]
consist of lowercase English letters.
All the strings of words
are unique .
Solutions
Solution 1
Python3 Java C++ Go
class Solution :
def indexPairs ( self , text : str , words : List [ str ]) -> List [ List [ int ]]:
words = set ( words )
n = len ( text )
return [
[ i , j ] for i in range ( n ) for j in range ( i , n ) if text [ i : j + 1 ] in words
]
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
36
37
38
39
40
41 class Trie {
Trie [] children = new Trie [ 26 ] ;
boolean isEnd = false ;
void insert ( String word ) {
Trie node = this ;
for ( char c : word . toCharArray ()) {
c -= 'a' ;
if ( node . children [ c ] == null ) {
node . children [ c ] = new Trie ();
}
node = node . children [ c ] ;
}
node . isEnd = true ;
}
}
class Solution {
public int [][] indexPairs ( String text , String [] words ) {
Trie trie = new Trie ();
for ( String w : words ) {
trie . insert ( w );
}
int n = text . length ();
List < int []> ans = new ArrayList <> ();
for ( int i = 0 ; i < n ; ++ i ) {
Trie node = trie ;
for ( int j = i ; j < n ; ++ j ) {
int idx = text . charAt ( j ) - 'a' ;
if ( node . children [ idx ] == null ) {
break ;
}
node = node . children [ idx ] ;
if ( node . isEnd ) {
ans . add ( new int [] { i , j });
}
}
}
return ans . toArray ( new int [ ans . size () ][ 2 ] );
}
}
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
36
37
38
39 class Trie {
public :
vector < Trie *> children ;
bool isEnd = false ;
Trie () {
children . resize ( 26 );
}
void insert ( string word ) {
Trie * node = this ;
for ( char c : word ) {
c -= 'a' ;
if ( ! node -> children [ c ]) node -> children [ c ] = new Trie ();
node = node -> children [ c ];
}
node -> isEnd = true ;
}
};
class Solution {
public :
vector < vector < int >> indexPairs ( string text , vector < string >& words ) {
Trie * trie = new Trie ();
for ( auto w : words ) trie -> insert ( w );
int n = text . size ();
vector < vector < int >> ans ;
for ( int i = 0 ; i < n ; ++ i ) {
Trie * node = trie ;
for ( int j = i ; j < n ; ++ j ) {
int idx = text [ j ] - 'a' ;
if ( ! node -> children [ idx ]) break ;
node = node -> children [ idx ];
if ( node -> isEnd ) ans . push_back ({ i , j });
}
}
return ans ;
}
};
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
36
37
38
39
40
41
42
43 type Trie struct {
children [ 26 ] * Trie
isEnd bool
}
func newTrie () * Trie {
return & Trie {}
}
func ( this * Trie ) insert ( word string ) {
node := this
for _ , c := range word {
idx := int ( c - 'a' )
if node . children [ idx ] == nil {
node . children [ idx ] = newTrie ()
}
node = node . children [ idx ]
}
node . isEnd = true
}
func indexPairs ( text string , words [] string ) [][] int {
trie := newTrie ()
for _ , w := range words {
trie . insert ( w )
}
n := len ( text )
var ans [][] int
for i := range text {
node := trie
for j := i ; j < n ; j ++ {
idx := int ( text [ j ] - 'a' )
if node . children [ idx ] == nil {
break
}
node = node . children [ idx ]
if node . isEnd {
ans = append ( ans , [] int { i , j })
}
}
}
return ans
}
Solution 2
GitHub