အခန်း ၁၅ - Tries

အခန်း ၁၄ မှာ Binary Search Tree က "ဘယ်ငယ်၊ ညာကြီး" rule နဲ့ တန်ဖိုးတွေကို စီထားပြီး $O(\log n)$ နဲ့ ရှာတာ လေ့လာခဲ့ပါတယ်။ ဒါပေမယ့် BST (ရော Hash Map အခန်း ၄ ပါ) က "တန်ဖိုး x အတိအကျ ရှိလား" ဆိုတာ ဖြေဖို့ ကောင်းပေမယ့် — "cat နဲ့ စတဲ့ စကားလုံး အကုန် ဘာတွေလဲ" မျိုး prefix (ရှေ့ဆုံး အပိုင်း) နဲ့ ရှာတဲ့ ပြဿနာမှာ မကောင်းပါ။

ဥပမာ — Hash Map ထဲ စကားလုံး တစ်သိန်း ထည့်ထားပြီး "app နဲ့ စတာ ဘယ်နှလုံးလဲ" မေးရင် — Hash Map က key တစ်ခုလုံး အတိအကျ ကိုက်မှ ရှာတာမို့ စကားလုံး တစ်သိန်းလုံး တစ်ခုချင်း prefix စစ်ရ ( $O(n \cdot L)$ — $n$ = စကားလုံး အရေအတွက်၊ $L$ = prefix အရှည်)။ ဒါက ဖုန်း keyboard က autocomplete, search box က suggestion မျိုး "စာရိုက်တိုင်း ချက်ချင်း ပြ" ရမယ့် နေရာမှာ နှေးလွန်းပါတယ်။

ဒီ ပြဿနာကို ဖြေဖို့ Trie (prefix tree လို့လည်း ခေါ်) ကို သုံးပါတယ် — စကားလုံးတွေကို စာလုံး (character) တစ်လုံးချင်း node အဖြစ် tree ပုံစံ သိမ်းထားတဲ့ data structure ဖြစ်ပါတယ်။ ဒီအခန်းမှာ Trie ဆိုတာ ဘာလဲ၊ insert/search/prefix ဘယ်လို လုပ်လဲ၊ Hash Table နဲ့ ဘာကွာလဲ၊ memory က ဘယ်လောက် ကုန်လဲ ဆိုတာတွေ လေ့လာပြီး classic ပြဿနာ ၄ ခုကို တစ်ဆင့်ချင်း ဖြေကြည့်ပါမယ်။

အမည်အကြောင်း: Trie ဆိုတာ retrieval (ပြန်ထုတ်ယူခြင်း) ကနေ လာတာဖြစ်ပြီး၊ "ထရိုင်း" (try) လို့ ဖတ်သူ ရော "ထရီး" (tree) လို့ ဖတ်သူ ရော ရှိပါတယ်။

Trie ဆိုတာ ဘာလဲ

Trie ဆိုတာ စကားလုံးတွေကို စာလုံး တစ်လုံးချင်းစီ node အဖြစ် သိမ်းထားတဲ့ tree ဖြစ်ပါတယ်။ အဓိက idea က — prefix တူတဲ့ စကားလုံးတွေ ဟာ tree ထဲမှာ လမ်းကြောင်း (path) အစ ပိုင်း တူတူ ကို မျှဝေသုံးတာ ဖြစ်ပါတယ်။

["cat", "car", "card", "dog"] ၄ လုံးကို Trie ထဲ သိမ်းကြည့်ရအောင် —

graph TD
    RT((root)) --> C[c]
    RT --> D1[d]
    C --> A[a]
    A --> T(("t ★"))
    A --> R(("r ★"))
    R --> D2(("d ★"))
    D1 --> O[o]
    O --> G(("g ★"))

★ = isEnd (ဒီ node မှာ စကားလုံး တစ်လုံး ဆုံး)။ စကားလုံးတွေကို ဒီလို ဖတ်ရ:

"cat": root → c → a → t★
"car": root → c → a → r★
"card": root → c → a → r → d★
"dog": root → d → o → g★

သတိထားရမှာ —

"ca" ဆိုတဲ့ prefix ကို cat, car, card ၃ လုံးလုံး မျှသုံးထားသည် (node c → a တစ်ကြောင်းတည်း)။
node တစ်ခုစီမှာ "ဒီမှာ စကားလုံး ဆုံးသလား" (isEnd) အမှတ်အသား ရှိရသည် — car (r★) နဲ့ card (d★) ကို ခွဲဖို့။ r က ဆုံးမှတ်ဖြစ်ပေမယ့် သူ့အောက်မှာ d ဆက်ရှိနေသေးသည်။
root က ဗလာ (စာလုံး မထား) — ဒါက "စကားလုံး အားလုံး စတဲ့ နေရာ" ဖြစ်သည်။

Trie node ကို code မှာ ဖော်ပြတာ —

class TrieNode {
    TrieNode[] children = new TrieNode[26];  // 'a'..'z' အတွက် ၂၆ ကွက်
    boolean isEnd = false;                   // ဒီ node မှာ စကားလုံး ဆုံးသလား
}

children ၂ မျိုး: Java မှာ အင်္ဂလိပ် lowercase ၂၆ လုံးသာ ဆိုရင် TrieNode[26] array သုံးတာ မြန်ပါတယ် (c - 'a' နဲ့ index ထုတ်)။

Insert — စကားလုံး ထည့်ခြင်း

Trie ထဲ စကားလုံး တစ်လုံး ထည့်တဲ့အခါ — root ကနေ စပြီး စာလုံး တစ်လုံးချင်း လိုက်ဆင်း သွားသည်။ လမ်းကြောင်း မရှိသေးရင် node အသစ် ဆောက်၊ ရှိပြီးသားဆို မျှသုံး။ နောက်ဆုံး စာလုံး ရောက်ရင် အဲ့ node ကို isEnd = true မှတ်သည်။

cat ရှိပြီးသား Trie ထဲ car ထည့်ကြည့်ရအောင် —

ထည့်: "car"
  root → 'c' ရှိပြီးသား → မျှသုံး (ဆင်း)
  c    → 'a' ရှိပြီးသား → မျှသုံး (ဆင်း)
  a    → 'r' မရှိ → node အသစ် ဆောက် (ဆင်း)
  r    → စကားလုံး ဆုံး → isEnd = true ★

         (root)              (root)
          |                   |
          c                   c
          |          →        |
          a                   a
          |                  / \
          t★                t★  r★   ← 'r' အသစ်၊ "ca" မျှသုံး

// Trie ထဲ word ထည့်
void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        int i = c - 'a';                          // 'a'→0, 'b'→1, ...
        if (node.children[i] == null) {
            node.children[i] = new TrieNode();    // လမ်းကြောင်း မရှိ → ဆောက်
        }
        node = node.children[i];                  // တစ်ဆင့် ဆင်း
    }
    node.isEnd = true;                            // နောက်ဆုံး → စကားလုံး ဆုံးမှတ်
}

Complexity: insert က စကားလုံး အရှည် $L$ အတိုင်းသာ ဆင်းရလို့ $O(L)$ ဖြစ်ပါတယ် — Trie ထဲ စကားလုံး ဘယ်နှလုံး ရှိရှိ ( $n$ ဘယ်လောက်ကြီးကြီး) insert က $L$ ပေါ်သာ မူတည်တာ အရေးကြီးပါတယ်။

Search — စကားလုံး ရှာခြင်း

စကားလုံး တစ်လုံး Trie ထဲ ရှိမရှိ ရှာတာက — insert လိုပဲ root ကနေ စာလုံး တစ်လုံးချင်း လိုက်ဆင်း ပြီး၊ ၂ ချက် စစ်ရသည် —

စာလုံး တစ်ခုခု အတွက် လမ်းကြောင်း မရှိ ရင် → false (မရှိ)။
စာလုံး အကုန် ဆင်းပြီး နောက်ဆုံး node မှာ isEnd == true မှ → true။ isEnd မဟုတ်ရင် ဒါက "prefix သာ ဖြစ်ပြီး စကားလုံး အပြည့် မဟုတ်" လို့ ဆိုလိုသည်။

ဒုတိယ ချက်က အရေးကြီးပါတယ် — card ထည့်ထားတဲ့ Trie မှာ car ရှာရင် လမ်းကြောင်း c→a→r တွေ့ပေမယ့်၊ r မှာ isEnd မဟုတ်ရင် card သာ ထည့်ထားပြီး car က မထည့်ရသေး လို့ ဆိုလိုပါတယ်။

// word အပြည့်အစုံ ရှိမရှိ
boolean search(String word) {
    TrieNode node = findNode(word);          // လမ်းကြောင်း လိုက်ဆင်း
    return node != null && node.isEnd;        // ဆုံးမှတ် ဖြစ်မှ true
}

// prefix လမ်းကြောင်း လိုက်ဆင်းပြီး နောက်ဆုံး node ပြန် (မရှိရင် null)
private TrieNode findNode(String prefix) {
    TrieNode node = root;
    for (char c : prefix.toCharArray()) {
        int i = c - 'a';
        if (node.children[i] == null) return null;   // လမ်းကြောင်း ပြတ် → မရှိ
        node = node.children[i];
    }
    return node;
}

Starts With — prefix နဲ့ ရှာခြင်း

Trie ရဲ့ အသက် က ဒီ operation ဖြစ်ပါတယ် — "pre ဆိုတဲ့ prefix နဲ့ စတဲ့ စကားလုံး တစ်ခုခု ရှိလား" ဆိုတာ စစ်တာ။ search နဲ့ ကွာတာ တစ်ခုတည်း — နောက်ဆုံး node မှာ isEnd စစ်စရာ မလိုပါ။ လမ်းကြောင်း ရှိရုံနဲ့ "ဒီ prefix နဲ့ စတာ ရှိတယ်" လို့ ဆိုနိုင်ပါတယ်။

   Trie: ["cat", "car", "card", "dog"]

   startsWith("ca")?  root→c→a လမ်းကြောင်း ရှိ → true ✓
   startsWith("do")?  root→d→o လမ်းကြောင်း ရှိ → true ✓
   startsWith("ba")?  root→'b' မရှိ → false ✗

// prefix နဲ့ စတဲ့ စကားလုံး ရှိမရှိ
boolean startsWith(String prefix) {
    return findNode(prefix) != null;     // လမ်းကြောင်း ရှိရုံ (isEnd မစစ်)
}

ဒါက ဘာကြောင့် Hash Map ထက် ကောင်းသလဲ: Hash Map နဲ့ "ca နဲ့ စတာ ရှိလား" မေးရင် key အကုန်လုံး ( $n$ လုံး) prefix စစ်ရ ( $O(n \cdot L)$ )။ Trie နဲ့ဆိုရင် prefix အရှည် $L$ အတိုင်းသာ ဆင်းရလို့ $O(L)$ — Trie ထဲ စကားလုံး ဘယ်နှသိန်း ရှိရှိ မမူတည်ပါ။

Memory Trade-off — Trie က နေရာ ဘယ်လောက် ကုန်လဲ

Trie က မြန်ပေမယ့် memory အတွက် ပေးဆပ်ရပါတယ်။ node တစ်ခုစီမှာ children pointer (Java မှာ TrieNode[26] — ၂၆ ကွက်) ထားရလို့ — စကားလုံး အနည်းငယ်သာ ထည့်ထားရင် ကွက်အများစု null ဖြစ်ပြီး နေရာ အလဟဿ ဖြစ်နိုင်ပါတယ်။

	Hash Map (Set)	Trie
Exact search ("word ရှိလား")	$O(L)$ မြန်	$O(L)$ မြန်
Prefix search ("ca နဲ့ စတာ ရှိလား")	$O(n \cdot L)$ နှေး	$O(L)$ မြန်
Memory	စကားလုံး အရွယ်အတိုင်း	များနိုင် (node/pointer အများ)
Sorted order	မရ (random)	ရ (စာလုံးအလိုက် စီပြီးသား)

ဘယ်ဟာ ဘယ်အချိန် သုံးမလဲ: "exact ရှိမရှိ" သာ လိုရင် → Hash Map (ရိုးရှင်း၊ memory သက်သာ)။ "prefix နဲ့ ရှာ / autocomplete / sorted order" လိုရင် → Trie။ ဒါက Trie ကို တကူးတက သုံးရတဲ့ အဓိက အကြောင်းပါ — prefix operation က Trie ရဲ့ ထူးခြားချက်ဖြစ်သည်။

Memory ချွေတာနည်း: စကားလုံး များပြားလာရင် node တွေ မြောက်မြားလာတာကို လျှော့ဖို့ Radix Tree (Compressed Trie) — "ကွဲစရာ မရှိတဲ့ string အပိုင်း" ကို node တစ်ခုတည်းမှာ ပေါင်းသိမ်းတဲ့ နည်း — ရှိပါတယ်။ ဒီစာအုပ်မှာ အသေးစိတ် မလေ့လာပေမယ့်၊ "Trie ကို memory အတွက် optimize လုပ်တဲ့ နည်း ရှိတယ်" ဆိုတာ မှတ်ထားပါ။

Real-world Examples

Trie ဟာ "prefix နဲ့ ရှာ / စာလုံးအလိုက် စီထား" လိုတဲ့ နေရာတိုင်းမှာ တွေ့ရပါတယ် —

Autocomplete — search box / ဖုန်း keyboard မှာ app ရိုက်တာနဲ့ "apple, application, apply..." prefix ကိုက်တာတွေ ချက်ချင်း ပြ။
Search Suggestion — Google search bar က စာလုံး တစ်လုံး ရိုက်တိုင်း အကြံပြုချက်တွေ ထွက်လာတာ။
Dictionary App — စာလုံး ရှိမရှိ စစ်ခြင်း၊ "ဒီ prefix နဲ့ စတဲ့ စကားလုံး အကုန်" စာရင်း ထုတ်ခြင်း။
Spell Checker — စာလုံး Trie ထဲ ရှိမရှိ စစ်၊ မရှိရင် prefix တူတာတွေနဲ့ ပြင်ဆင်ချက် အကြံပြု။
Command / IP Route Matching — terminal command auto-complete၊ router က IP address ကို "longest prefix match" နဲ့ လမ်းကြောင်း ရွေး။

ဒီ pattern တွေ အကုန်လုံး "စာလုံး အစ ပိုင်း (prefix) တူတာတွေကို အမြန် စုစည်း/ရှာ" ဆိုတဲ့ အခြေအနေပါ — Trie က prefix ကို မျှသုံးထားလို့ ဒီအလုပ်ကို သဘာဝကျကျ လုပ်ပေးနိုင်တာ ဖြစ်ပါတယ်။

Questions

Trie ကို လက်တွေ့ ပြဿနာ ၄ ခုနဲ့ ချိတ်ဆက် လေ့လာကြည့်ရအောင်။ ပြဿနာတိုင်းရဲ့ သော့ချက်က — စကားလုံးတွေကို စာလုံးအလိုက် node ပြောင်းပြီး prefix မျှသုံးတဲ့ Trie structure ကို အသုံးချတတ်ဖို့ ဖြစ်ပါတယ်။

၁။ Implement Trie (Prefix Tree)

insert, search, startsWith ၃ ခု ပါတဲ့ Trie class ကို တည်ဆောက်ပါ။

Example 1:

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");     // true   (အပြည့်အစုံ ရှိ)
trie.search("app");       // false  (လမ်းကြောင်း ရှိပေမယ့် isEnd မဟုတ်)
trie.startsWith("app");   // true   (prefix ရှိ)
trie.insert("app");
trie.search("app");       // true   (အခု ထည့်ပြီးပြီ)

ရှင်းလင်းချက်

ဒါက အပေါ်က insert / search / startsWith ၃ ခုကို တစ်စုတည်း စုစည်းတာ ဖြစ်ပါတယ်။ သော့ချက် ၂ ချက် —

node တစ်ခုစီမှာ children (နောက်စာလုံးတွေ) နဲ့ isEnd (ဆုံးမှတ်လား) ၂ ခု ထား။
search က isEnd စစ်သည်၊ startsWith က လမ်းကြောင်း ရှိရုံ စစ်သည် — ဒါက ၂ ခုရဲ့ တစ်ခုတည်းသော ကွာခြားချက်။

Time Complexity: insert/search/startsWith အားလုံး $O(L)$ - စကားလုံး/prefix အရှည်။
Space Complexity: insert အတွက် $O(L)$ (node အသစ် အများဆုံး $L$ ခု)။

Java Solution

class Trie {
    private TrieNode root = new TrieNode();

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

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new TrieNode();
            node = node.children[i];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = find(word);
        return node != null && node.isEnd;       // ဆုံးမှတ် ဖြစ်မှ
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;             // လမ်းကြောင်း ရှိရုံ
    }

    private TrieNode find(String s) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) return null;
            node = node.children[i];
        }
        return node;
    }
}

၂။ Word Search II

m × n စာလုံး grid board နဲ့ စကားလုံး စာရင်း words ပေးထားသည်။ grid ထဲ — အနီးကပ် (အပေါ်/အောက်/ဘယ်/ညာ) ကွက်တွေ ဆက်တိုက် ဖတ်ပြီး ဖွဲ့လို့ ရတဲ့ စကားလုံး အကုန် ကို ပြန်ပါ။ ကွက်တစ်ခုကို စကားလုံး တစ်လုံးအတွင်း တစ်ခါသာ သုံးရသည်။

Example 1:

Input: board = [["o","a","a","n"],
                ["e","t","a","e"],
                ["i","h","k","r"],
                ["i","f","l","v"]]
       words = ["oath","pea","eat","rain"]
Output: ["oath","eat"]
   ("oath": o→a→t→h လမ်းကြောင်း ရှိ၊  "eat": e→a→t ရှိ၊  "pea"/"rain" မရှိ)

ရှင်းလင်းချက်

စကားလုံး တစ်လုံးချင်း grid မှာ ရှာ (DFS) လုပ်ရင် — words များလာ၊ grid ကြီးလာတဲ့အခါ ထပ်ခါတလဲလဲ ဖြတ်ရလို့ နှေးပါတယ်။ သော့ချက်က — words အကုန်လုံးကို Trie ထဲ ထည့်ပြီး၊ grid ကို တစ်ခါတည်း DFS ဖြတ်ရင်း Trie လမ်းကြောင်းကို တပြိုင်တည်း လိုက်တာ ဖြစ်ပါတယ်။

grid ကွက်တစ်ခုစီကနေ DFS စ — လက်ရှိ စာလုံးက Trie node မှာ child ရှိမှ ဆက်ဖြတ် (မရှိရင် ချက်ချင်း ရပ် = pruning)။
Trie node မှာ isEnd တွေ့ရင် → အဲ့ စကားလုံး တွေ့ပြီ → result ထဲ ထည့်။
ကွက်ကို "သုံးပြီ" အမှတ်အသား လုပ် (Choose) → ၄ ဘက် ဆက်ဖြတ် (Explore) → ပြန်ဖြုတ် (Undo — အခန်း ၁၆ backtracking ပုံစံ)။

Trie ကြောင့် — "ဒီ prefix နဲ့ စတဲ့ စကားလုံး တစ်လုံးမှ မရှိ" ဆိုတာ သိတာနဲ့ grid လမ်းကြောင်းကို ချက်ချင်း ဖြတ်ပစ်လို့၊ စကားလုံး တစ်လုံးချင်း သီးခြား ရှာတာထက် များစွာ မြန်ပါတယ်။

Time Complexity: အကြမ်းဖျင်း $O(M \cdot 4 \cdot 3^{L})$ - grid ကွက် $M$ ခု၊ DFS အမြင့် $L$ (စကားလုံး အရှည်ဆုံး)။ Trie က prune လုပ်လို့ လက်တွေ့မှာ ပိုမြန်။
Space Complexity: $O(K)$ - Trie size (words စုစုပေါင်း စာလုံး အရေအတွက်)။

Java Solution

class Solution {
    private List<String> result = new ArrayList<>();

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = buildTrie(words);                // words → Trie
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfs(board, r, c, root);                   // ကွက်တိုင်းကနေ စ
            }
        }
        return result;
    }

    private void dfs(char[][] board, int r, int c, TrieNode node) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return;
        char ch = board[r][c];
        if (ch == '#' || node.children[ch - 'a'] == null) return;  // သုံးပြီး / prune
        node = node.children[ch - 'a'];
        if (node.word != null) {                         // isEnd → စကားလုံး တွေ့ပြီ
            result.add(node.word);
            node.word = null;                            // ထပ် မထည့်အောင်
        }
        board[r][c] = '#';                               // 1. Choose (သုံးပြီ မှတ်)
        dfs(board, r + 1, c, node);                      // 2. Explore (၄ ဘက်)
        dfs(board, r - 1, c, node);
        dfs(board, r, c + 1, node);
        dfs(board, r, c - 1, node);
        board[r][c] = ch;                                // 3. Undo (ပြန်ဖြုတ်)
    }

    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (node.children[i] == null) node.children[i] = new TrieNode();
                node = node.children[i];
            }
            node.word = w;                               // ဆုံးမှတ်မှာ စကားလုံး သိမ်း
        }
        return root;
    }

    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;                              // isEnd အစား စကားလုံး သိမ်း
    }
}

၃။ Replace Words (Shortest Root)

အမြစ်စကားလုံး (root) စာရင်း dictionary နဲ့ ဝါကျ sentence ပေးထားသည်။ ဝါကျထဲက စကားလုံး တစ်ခုစီအတွက် — အဲ့စကားလုံးကို prefix အဖြစ် ထားနိုင်တဲ့ အတိုဆုံး root နဲ့ အစားထိုးပါ။ root မရှိရင် မူရင်းအတိုင်း ထား။

Example 1:

Input: dictionary = ["cat","bat","rat"]
       sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
   ("cattle"→"cat", "rattled"→"rat", "battery"→"bat")

ရှင်းလင်းချက်

root တွေကို Trie ထဲ ထည့်ထားပြီး — ဝါကျက စကားလုံး တစ်ခုစီကို Trie ထဲ စာလုံးချင်း ဆင်းရင်း isEnd တွေ့တာနဲ့ ရပ် ရပါတယ်။ isEnd ပထမဆုံး တွေ့တဲ့ နေရာက အတိုဆုံး root ဖြစ်ပါတယ် (တိုတိုက အရင် ဆုံးတာမို့)။

စကားလုံးကို Trie မှာ စာလုံးချင်း ဆင်း။
isEnd တွေ့ → အဲ့အထိ prefix က root → အစားထိုး။
လမ်းကြောင်း ပြတ် (child မရှိ) သို့ စကားလုံး ကုန်တဲ့အထိ isEnd မတွေ့ → မူရင်း ထား။

Time Complexity: $O(M + N)$ - $M$ = dictionary စာလုံး စုစုပေါင်း (root တွေ Trie ထဲ insert)၊ $N$ = ဝါကျ စာလုံး စုစုပေါင်း (lookup)။
Space Complexity: $O(M)$ - dictionary စုစုပေါင်း စာလုံး အရေအတွက် (Trie size)။

Java Solution

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = new TrieNode();
        for (String w : dictionary) insert(root, w);     // root အကုန် ထည့်

        StringBuilder sb = new StringBuilder();
        for (String word : sentence.split(" ")) {
            if (sb.length() > 0) sb.append(" ");
            sb.append(shortestRoot(root, word));         // တစ်လုံးချင်း အစားထိုး
        }
        return sb.toString();
    }

    private String shortestRoot(TrieNode root, String word) {
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) return word;   // လမ်းကြောင်း ပြတ် → မူရင်း
            prefix.append(c);
            node = node.children[i];
            if (node.isEnd) return prefix.toString();    // ပထမ root → အတိုဆုံး
        }
        return word;                                     // root မဆုံး → မူရင်း
    }

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

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

၄။ Longest Common Prefix

စကားလုံး array strs ပေးထားသည်။ အကုန်လုံးမှာ တူညီတဲ့ အရှည်ဆုံး ရှေ့ဆုံး အပိုင်း (longest common prefix) ကို ပြန်ပါ။ မရှိရင် "" ပြန်ပါ။

Example 1:

Input: strs = ["flower", "flow", "flight"]
Output: "fl"
   (၃ လုံးလုံး "fl" နဲ့ စ၊ ဒါပေမယ့် "flo" က "flight" မှာ မရှိ)

ရှင်းလင်းချက်

ဒါကို Trie idea နဲ့ စဉ်းစားနိုင်ပါတယ် — စကားလုံး အကုန် Trie ထဲ ထည့်ရင်၊ common prefix ဆိုတာ root ကနေ "လမ်းခွဲ မရှိဘဲ (child ၁ ခုတည်း) ဆက်ဆင်းနိုင်တဲ့" အပိုင်း ဖြစ်ပါတယ်။ လမ်းခွဲ ( $\geq 2$ children) တွေ့တာ သို့ စကားလုံး တစ်ခု ဆုံး (isEnd) တာနဲ့ common prefix ရပ်ပါတယ်။

ပိုရိုးတဲ့နည်း: ဒီပြဿနာအတွက် Trie တကယ် မဆောက်ဘဲ — ပထမ စကားလုံးကို စံထား၊ ကျန်တာနဲ့ စာလုံးချင်း တိုက်စစ်ပြီး ကွဲတဲ့ နေရာမှာ ဖြတ်ရင် ပိုလွယ်ပါတယ် (idea အတူတူ — "လမ်းခွဲ မဖြစ်မချင်း ဆက်သွား")။ အောက်မှာ ဒီနည်းကို ပြထားသည်။

Time Complexity: $O(N)$ - စာလုံး စုစုပေါင်း (အဆိုးဆုံး အကုန် တိုက်စစ်)။
Space Complexity: $O(1)$ - extra space မလို။

Java Solution

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        // ပထမ စကားလုံးကို စံထား၊ စာလုံး (column) တစ်လုံးချင်း တိုက်စစ်
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                // အဲ့ စကားလုံး ကုန်ပြီ သို့ စာလုံး မကိုက် → အဲ့အထိ ပြန်
                if (i == strs[j].length() || strs[j].charAt(i) != c)
                    return strs[0].substring(0, i);      // final substring တစ်ခုတည်း
            }
        }
        return strs[0];
    }
}