Index Pairs of a String

class Solution {
    struct Node {
        Node* child[26]{};
        bool isEnd = false;
    };
    void insert(Node* root, const string& w) {
        Node* cur = root;
        for (char c : w) {
            int i = c - 'a';
            if (!cur->child[i]) cur->child[i] = new Node();
            cur = cur->child[i];
        }
        cur->isEnd = true;
    }
public:
    vector<vector<int>> indexPairs(string text, vector<string>& words) {
        Node* root = new Node();
        for (auto& w : words) insert(root, w);
        vector<vector<int>> ans;
        int n = text.size();
        for (int i = 0; i < n; ++i) {
            Node* cur = root;
            for (int j = i; j < n; ++j) {
                int idx = text[j] - 'a';
                if (!cur->child[idx]) break;
                cur = cur->child[idx];
                if (cur->isEnd) ans.push_back({i, j});
            }
        }
        return ans;
    }
};

type trieNode struct {
    child [26]*trieNode
    isEnd bool
}

func insert(root *trieNode, w string) {
    cur := root
    for i := 0; i < len(w); i++ {
        idx := w[i] - 'a'
        if cur.child[idx] == nil {
            cur.child[idx] = &trieNode{}
        }
        cur = cur.child[idx]
    }
    cur.isEnd = true
}

func indexPairs(text string, words []string) [][]int {
    root := &trieNode{}
    for _, w := range words {
        insert(root, w)
    }
    ans := [][]int{}
    n := len(text)
    for i := 0; i < n; i++ {
        cur := root
        for j := i; j < n; j++ {
            idx := text[j] - 'a'
            if cur.child[idx] == nil {
                break
            }
            cur = cur.child[idx]
            if cur.isEnd {
                ans = append(ans, []int{i, j})
            }
        }
    }
    return ans
}

from typing import List

class Solution:
    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
        TRIE: dict = {}
        for w in words:
            cur = TRIE
            for ch in w:
                cur = cur.setdefault(ch, {})
            cur['$'] = True

        ans: List[List[int]] = []
        n = len(text)
        for i in range(n):
            cur = TRIE
            for j in range(i, n):
                ch = text[j]
                if ch not in cur:
                    break
                cur = cur[ch]
                if cur.get('$'):
                    ans.append([i, j])
        return ans

function indexPairs(text, words) {
    const TRIE = {};
    for (const w of words) {
        let cur = TRIE;
        for (const ch of w) {
            if (!cur[ch]) cur[ch] = {};
            cur = cur[ch];
        }
        cur.$ = true;
    }

    const ans = [];
    const n = text.length;
    for (let i = 0; i < n; i++) {
        let cur = TRIE;
        for (let j = i; j < n; j++) {
            const ch = text[j];
            if (!cur[ch]) break;
            cur = cur[ch];
            if (cur.$) ans.push([i, j]);
        }
    }
    return ans;
}

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

class Solution {
    private void insert(TrieNode root, String w) {
        TrieNode cur = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) cur.children[i] = new TrieNode();
            cur = cur.children[i];
        }
        cur.isEnd = true;
    }

    public int[][] indexPairs(String text, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) insert(root, w);
        List<int[]> ans = new ArrayList<>();
        int n = text.length();
        for (int i = 0; i < n; i++) {
            TrieNode cur = root;
            for (int j = i; j < n; j++) {
                int idx = text.charAt(j) - 'a';
                if (cur.children[idx] == null) break;
                cur = cur.children[idx];
                if (cur.isEnd) ans.add(new int[]{i, j});
            }
        }
        return ans.toArray(new int[0][]);
    }
}

type TrieMap = { [ch: string]: TrieMap | boolean | undefined };

function indexPairs(text: string, words: string[]): number[][] {
    const TRIE: TrieMap = {};
    for (const w of words) {
        let cur: TrieMap = TRIE;
        for (const ch of w) {
            if (!cur[ch]) cur[ch] = {};
            cur = cur[ch] as TrieMap;
        }
        cur.$ = true;
    }

    const ans: number[][] = [];
    const n = text.length;
    for (let i = 0; i < n; i++) {
        let cur: TrieMap | undefined = TRIE;
        for (let j = i; j < n; j++) {
            const ch = text[j];
            if (!cur || !cur[ch]) break;
            cur = cur[ch] as TrieMap;
            if (cur.$) ans.push([i, j]);
        }
    }
    return ans;
}