🚀 0ms Solution! Beating 100%  with Super Scott's Prefix Power and Trie! ⚡🔥
🦸 Super Scott's Coding Crusade! 🦸‍♂️"Listen up, hero! Prefixes are the first step in a word’s journey — just like the opening chapter of your life. Pay attentio
# 🦸 Super Scott's Coding Crusade! 🦸‍♂️

"Listen up, hero! Prefixes are the first step in a word’s journey — just like the opening chapter of your life. Pay attention, because every detail matters!" – Super Scott

---
![image.png](https://assets.leetcode.com/users/images/12a77db8-8aa8-481e-8fc4-b99c6275115c_1736387312.8344545.png)
## 🧐 **Understanding the Problem**

Super Scott has a mission for you:  
You're given a list of words and a prefix. Your task is to count how many words in the list **start with that prefix**. Let’s break this heroic mission down step by step.

---

### **What is a Prefix?**

A prefix is the starting portion of a word. Think of it like the opening scene of a blockbuster superhero movie. Here are some examples:  
- In the word `"attention"`, prefixes are: `"a"`, `"at"`, `"att"`, `"atte"`, and so on.  
- For the prefix `"at"`, the words `"attention"` and `"attend"` match, but `"pay"` does not.

---

### **Mission Objective**

1. **Inspect the Words**: For each word in the list, check if it starts with the given prefix.
2. **Count the Matches**: Keep track of how many words match the prefix.
3. **Return the Count**: At the end of the quest, report how many words were victorious.

---

### **Examples from Super Scott's Archive**

#### Example 1:
- **Input**:  
  `words = ["pay", "attention", "practice", "attend"]`  
  `pref = "at"`
- **Output**:  
  `2`
- **Explanation**:  
  The words `"attention"` and `"attend"` begin with `"at"`.

#### Example 2:
- **Input**:  
  `words = ["leetcode", "win", "loops", "success"]`  
  `pref = "code"`
- **Output**:  
  `0`
- **Explanation**:  
  No word starts with `"code"`.

---

### **Super Scott’s Wisdom**
"Code like a hero, inspect every word, and honor the prefix — because in the world of programming, every detail counts!" – Super Scott

---

### **Solution 1** 💻

```python3 []
class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        l = len(pref)  # Length of the prefix
        ans = 0  # Counter for words with the prefix
        for word in words:
            if len(word) >= l and word[:l] == pref:  # Check if the word starts with the prefix
                ans += 1
        return ans
```
``` java []
class Solution {
    public int prefixCount(String[] words, String pref) {
        int ans = 0;
        int len = pref.length();
        for (String word : words) {
            if (word.length() >= len && word.substring(0, len).equals(pref)) {
                ans++;
            }
        }
        return ans;
    }
}


```
``` cpp []
class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        int ans = 0;
        int len = pref.length();
        for (string& word : words) {
            if (word.length() >= len && word.substr(0, len) == pref) {
                ans++;
            }
        }
        return ans;
    }
};

```
``` javascript []
var prefixCount = function(words, pref) {
    let ans = 0;
    const len = pref.length;
    for (let word of words) {
        if (word.length >= len && word.slice(0, len) === pref) {
            ans++;
        }
    }
    return ans;
};
```
``` csharp []
using System;

public class Solution {
    public int PrefixCount(string[] words, string pref) {
        int ans = 0;
        int len = pref.Length;
        foreach (var word in words) {
            if (word.Length >= len && word.Substring(0, len) == pref) {
                ans++;
            }
        }
        return ans;
    }
}
```
``` ruby []
def prefix_count(words, pref)
    ans = 0
    len = pref.length
    words.each do |word|
        if word.length >= len && word[0, len] == pref
            ans += 1
        end
    end
    ans
end
```
``` go []
package main

import "fmt"

func prefixCount(words []string, pref string) int {
    ans := 0
    l := len(pref)
    for _, word := range words {
        if len(word) >= l && word[:l] == pref {
            ans++
        }
    }
    return ans
}
```
### **Explanation of the Code**

1. **Measure the Prefix**:  
   First, calculate the length of the prefix (`l`) since we’ll compare only the first `l` characters of each word.

2. **Loop Through the Words**:  
   For every word in the list:  
   - Check if its length is at least as long as the prefix.  
   - Compare the first `l` characters with the prefix.  
   - If it matches, increment the count.

3. **Return the Count**:  
   Once all words have been checked, return the final count.

---
### 🧑‍🏫 **Time Complexity Analysis:**

#### **Time Complexity:**
For each word in the list `words`, we compare the first `l` characters (where `l` is the length of the prefix `pref`) to check if it matches the prefix.  
This takes **O(l)** time for each word.  
Thus, if there are `n` words in `words`, the overall time complexity is **O(n * l)**, where `n` is the number of words and `l` is the length of the prefix.

#### **Space Complexity:**
The space complexity is **O(1)** because we are only using a few variables (`ans`, `l`), and the space used does not grow with the input size.

___
___

# **Solution 2** 💻

## Trie Data Structure for Prefix Count Solution

We use a **Trie** (also known as a prefix tree) to efficiently handle the word counting problem based on prefixes.

### What is a Trie?
A Trie is a tree-like data structure that stores strings in a way that allows for efficient querying of prefixes and exact matches. Each node in the Trie corresponds to a character in a word, and we can use it to store the number of words that share a certain prefix.

### Key Operations:

1. **Add Operation**:
   - For each word, we insert it character by character into the Trie.
   - We increment `startc` for every character of the word to indicate how many words share the same prefix.
   - We increment `endc` at the last character of the word to indicate that this is the end of a valid word.

2. **StartsWith Operation**:
   - To check how many words start with a given prefix, we return the `startc` value of the last character node of the prefix.

### Time Complexity:
- **Add**: O(n), where n is the length of the word being inserted.
- **StartsWith**: O(n), where n is the length of the prefix.

### Space Complexity:
- O(m * n), where m is the number of unique characters and n is the total number of characters inserted. This accounts for the storage of each character in the Trie nodes.

---

### Code Implementation:
```python3 []
class Node:
    def __init__(self):
        self.dicto = {}
        self.startc = 0

class Trie:
    def __init__(self):
        self.head = Node()

    # Method to insert a word into the Trie
    def add(self, word):
        curr = self.head
        for char in word:
            if char not in curr.dicto:
                curr.dicto[char] = Node()
            curr = curr.dicto[char]
            curr.startc += 1

    # Method to count how many words start with the given prefix
    def startsWith(self, prefix):
        curr = self.head
        for char in prefix:
            if char not in curr.dicto:
                return 0
            curr = curr.dicto[char]
        return curr.startc

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        # Create a Trie and insert all words into it
        trie = Trie()
        for word in words:
            trie.add(word)
        
        # Use the Trie to find how many words start with the prefix
        return trie.startsWith(pref)
```
``` java []
import java.util.HashMap;

class TrieNode {
    HashMap<Character, TrieNode> dict = new HashMap<>();
    int startCount = 0;
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void add(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            current.dict.putIfAbsent(c, new TrieNode());
            current = current.dict.get(c);
            current.startCount++;
        }
    }

    public int startsWith(String prefix) {
        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            if (!current.dict.containsKey(c)) {
                return 0;
            }
            current = current.dict.get(c);
        }
        return current.startCount;
    }
}

public class Solution {
    public int prefixCount(String[] words, String pref) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.add(word);
        }
        return trie.startsWith(pref);
    }
}
```
``` cpp []
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> dict;
    int startCount = 0;
};

class Trie {
public:
    TrieNode* root;
    
    Trie() {
        root = new TrieNode();
    }
    
    void add(string word) {
        TrieNode* current = root;
        for (char c : word) {
            if (current->dict.find(c) == current->dict.end()) {
                current->dict[c] = new TrieNode();
            }
            current = current->dict[c];
            current->startCount++;
        }
    }
    
    int startsWith(string prefix) {
        TrieNode* current = root;
        for (char c : prefix) {
            if (current->dict.find(c) == current->dict.end()) {
                return 0;
            }
            current = current->dict[c];
        }
        return current->startCount;
    }
};

class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        Trie trie;
        for (string word : words) {
            trie.add(word);
        }
        return trie.startsWith(pref);
    }
};
```
``` csharp []
using System;
using System.Collections.Generic;

public class TrieNode {
    public Dictionary<char, TrieNode> Dict = new Dictionary<char, TrieNode>();
    public int StartCount = 0;
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void Add(string word) {
        TrieNode current = root;
        foreach (char c in word) {
            if (!current.Dict.ContainsKey(c)) {
                current.Dict[c] = new TrieNode();
            }
            current = current.Dict[c];
            current.StartCount++;
        }
    }

    public int StartsWith(string prefix) {
        TrieNode current = root;
        foreach (char c in prefix) {
            if (!current.Dict.ContainsKey(c)) {
                return 0;
            }
            current = current.Dict[c];
        }
        return current.StartCount;
    }
}

public class Solution {
    public int PrefixCount(string[] words, string pref) {
        Trie trie = new Trie();
        foreach (string word in words) {
            trie.Add(word);
        }
        return trie.StartsWith(pref);
    }
}
```
``` go []
package main

import "fmt"

type TrieNode struct {
	dicto     map[rune]*TrieNode
	startCount int
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{root: &TrieNode{dicto: make(map[rune]*TrieNode)}}
}

func (t *Trie) Add(word string) {
	current := t.root
	for _, c := range word {
		if _, ok := current.dicto[c]; !ok {
			current.dicto[c] = &TrieNode{dicto: make(map[rune]*TrieNode)}
		}
		current = current.dicto[c]
		current.startCount++
	}
}

func (t *Trie) StartsWith(prefix string) int {
	current := t.root
	for _, c := range prefix {
		if _, ok := current.dicto[c]; !ok {
			return 0
		}
		current = current.dicto[c]
	}
	return current.startCount
}

func prefixCount(words []string, pref string) int {
	trie := NewTrie()
	for _, word := range words {
		trie.Add(word)
	}
	return trie.StartsWith(pref)
}

```
``` ruby []
class TrieNode
  attr_accessor :dict, :start_count

  def initialize
    @dict = {}
    @start_count = 0
  end
end

class Trie
  def initialize
    @root = TrieNode.new
  end

  def add(word)
    curr = @root
    word.each_char do |char|
      curr.dict[char] ||= TrieNode.new
      curr = curr.dict[char]
      curr.start_count += 1
    end
  end

  def starts_with(prefix)
    curr = @root
    prefix.each_char do |char|
      return 0 unless curr.dict[char]
      curr = curr.dict[char]
    end
    curr.start_count
  end
end

class Solution
  def prefix_count(words, pref)
    trie = Trie.new
    words.each { |word| trie.add(word) }
    trie.starts_with(pref)
  end
end
```
``` javascript []
class TrieNode {
    constructor() {
        this.dicto = {};
        this.startCount = 0;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    add(word) {
        let current = this.root;
        for (let char of word) {
            if (!current.dicto[char]) {
                current.dicto[char] = new TrieNode();
            }
            current = current.dicto[char];
            current.startCount++;
        }
    }

    startsWith(prefix) {
        let current = this.root;
        for (let char of prefix) {
            if (!current.dicto[char]) {
                return 0;
            }
            current = current.dicto[char];
        }
        return current.startCount;
    }
}

function prefixCount(words, pref) {
    const trie = new Trie();
    for (let word of words) {
        trie.add(word);
    }
    return trie.startsWith(pref);
}
```
### **Victory Awaits!**

Go ahead, implement this and watch as your prefix-matching powers save the day! 💪✨
![WhatsApp Image 2025-01-09 at 07.24.25_0d0e547b.jpg](https://assets.leetcode.com/users/images/9b431867-2c5b-4591-81ab-5aeb7ccb8201_1736387702.7284853.jpeg)




['Trie', 'C++', 'Java', 'Python3', 'Ruby', 'JavaScript', 'C#']