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.

• Java
• Python
• C++
• Go

• 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