Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1065.html

1065. Index Pairs of a String

Level

Easy

Description

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

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

Note:

  1. All strings contains only lowercase English letters.
  2. It’s guaranteed that all strings in words are different.
  3. 1 <= text.length <= 100
  4. 1 <= words.length <= 20
  5. 1 <= words[i].length <= 50
  6. Return the pairs [i,j] in sorted order (i.e. sort them by their first coordinate in case of ties sort them by their second coordinate).

Solution

For each word in words, find all occurrences of word in text, and add the index pairs to the result list. Sort the result list and return.

  • class Solution {
        public int[][] indexPairs(String text, String[] words) {
            List<int[]> indexPairsList = new ArrayList<int[]>();
            for (String word : words) {
                int wordLength = word.length();
                int curIndex = 0;
                while (curIndex >= 0) {
                    curIndex = text.indexOf(word, curIndex);
                    if (curIndex >= 0) {
                        indexPairsList.add(new int[]{curIndex, curIndex + wordLength - 1});
                        curIndex++;
                    }
                }
            }
            Collections.sort(indexPairsList, new Comparator<int[]>() {
                public int compare(int[] array1, int[] array2) {
                    if (array1[0] != array2[0])
                        return array1[0] - array2[0];
                    else
                        return array1[1] - array2[1];
                }
            });
            int length = indexPairsList.size();
            int[][] indexPairs = new int[length][2];
            for (int i = 0; i < length; i++) {
                int[] indexPair = indexPairsList.get(i);
                indexPairs[i][0] = indexPair[0];
                indexPairs[i][1] = indexPair[1];
            }
            return indexPairs;
        }
    }
    
  • class Trie:
        def __init__(self):
            self.children = [None] * 26
            self.is_end = False
    
        def insert(self, word):
            node = self
            for c in word:
                idx = ord(c) - ord('a')
                if node.children[idx] is None:
                    node.children[idx] = Trie()
                node = node.children[idx]
            node.is_end = True
    
    
    class Solution:
        def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
            trie = Trie()
            for w in words:
                trie.insert(w)
            n = len(text)
            ans = []
            for i in range(n):
                node = trie
                for j in range(i, n):
                    idx = ord(text[j]) - ord('a')
                    if node.children[idx] is None:
                        break
                    node = node.children[idx]
                    if node.is_end:
                        ans.append([i, j])
            return ans
    
    
    
  • 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;
        }
    };
    
  • 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
    }
    

All Problems

All Solutions