Welcome to Subscribe On Youtube

2185. Counting Words With a Given Prefix

Description

You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

A prefix of a string s is any leading contiguous substring of s.

 

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: The 2 strings that contain "at" as a prefix are: "attention" and "attend".

Example 2:

Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: There are no strings that contain "code" as a prefix.

 

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length, pref.length <= 100
• words[i] and pref consist of lowercase English letters.

Solutions

• Java
• C++
• Python
• Go
• TypeScript
• Rust
• Java 2
• C++ 2
• C
• Python 2
• Go 2

• class Solution {
      public int prefixCount(String[] words, String pref) {
          int ans = 0;
          for (String w : words) {
              if (w.startsWith(pref)) {
                  ++ans;
              }
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int prefixCount(vector<string>& words, string pref) {
          int ans = 0;
          for (auto& w : words) ans += w.find(pref) == 0;
          return ans;
      }
  };
  

• class Solution:
      def prefixCount(self, words: List[str], pref: str) -> int:
          return sum(w.startswith(pref) for w in words)
  
  

• func prefixCount(words []string, pref string) (ans int) {
  	for _, w := range words {
  		if strings.HasPrefix(w, pref) {
  			ans++
  		}
  	}
  	return
  }
  

• function prefixCount(words: string[], pref: string): number {
      return words.reduce((r, s) => (r += s.startsWith(pref) ? 1 : 0), 0);
  }
  
  

• impl Solution {
      pub fn prefix_count(words: Vec<String>, pref: String) -> i32 {
          words
              .iter()
              .filter(|s| s.starts_with(&pref))
              .count() as i32
      }
  }
  
  

• class Trie {
      private Trie[] children = new Trie[26];
      private int cnt;
  
      public void insert(String w) {
          Trie node = this;
          for (int i = 0; i < w.length(); ++i) {
              int j = w.charAt(i) - 'a';
              if (node.children[j] == null) {
                  node.children[j] = new Trie();
              }
              node = node.children[j];
              ++node.cnt;
          }
      }
  
      public int search(String pref) {
          Trie node = this;
          for (int i = 0; i < pref.length(); ++i) {
              int j = pref.charAt(i) - 'a';
              if (node.children[j] == null) {
                  return 0;
              }
              node = node.children[j];
          }
          return node.cnt;
      }
  }
  
  class Solution {
      public int prefixCount(String[] words, String pref) {
          Trie tree = new Trie();
          for (String w : words) {
              tree.insert(w);
          }
          return tree.search(pref);
      }
  }
  

• class Trie {
  public:
      Trie()
          : children(26)
          , cnt(0) {}
  
      void insert(string w) {
          Trie* node = this;
          for (auto& c : w) {
              int i = c - 'a';
              if (!node->children[i]) {
                  node->children[i] = new Trie();
              }
              node = node->children[i];
              ++node->cnt;
          }
      }
  
      int search(string pref) {
          Trie* node = this;
          for (auto& c : pref) {
              int i = c - 'a';
              if (!node->children[i]) {
                  return 0;
              }
              node = node->children[i];
          }
          return node->cnt;
      }
  
  private:
      vector<Trie*> children;
      int cnt;
  };
  
  class Solution {
  public:
      int prefixCount(vector<string>& words, string pref) {
          Trie* tree = new Trie();
          for (auto& w : words) {
              tree->insert(w);
          }
          return tree->search(pref);
      }
  };
  

• int prefixCount(char** words, int wordsSize, char* pref) {
      int ans = 0;
      int n = strlen(pref);
      for (int i = 0; i < wordsSize; i++) {
          if (strncmp(words[i], pref, n) == 0) {
              ans++;
          }
      }
      return ans;
  }
  

• class Trie:
      def __init__(self):
          self.children = [None] * 26
          self.cnt = 0
  
      def insert(self, w):
          node = self
          for c in w:
              i = ord(c) - ord('a')
              if node.children[i] is None:
                  node.children[i] = Trie()
              node = node.children[i]
              node.cnt += 1
  
      def search(self, pref):
          node = self
          for c in pref:
              i = ord(c) - ord('a')
              if node.children[i] is None:
                  return 0
              node = node.children[i]
          return node.cnt
  
  
  class Solution:
      def prefixCount(self, words: List[str], pref: str) -> int:
          tree = Trie()
          for w in words:
              tree.insert(w)
          return tree.search(pref)
  
  

• type Trie struct {
  	children [26]*Trie
  	cnt      int
  }
  
  func newTrie() *Trie {
  	return &Trie{}
  }
  
  func (this *Trie) insert(w string) {
  	node := this
  	for _, c := range w {
  		c -= 'a'
  		if node.children[c] == nil {
  			node.children[c] = newTrie()
  		}
  		node = node.children[c]
  		node.cnt++
  	}
  }
  
  func (this *Trie) search(pref string) int {
  	node := this
  	for _, c := range pref {
  		c -= 'a'
  		if node.children[c] == nil {
  			return 0
  		}
  		node = node.children[c]
  	}
  	return node.cnt
  }
  
  func prefixCount(words []string, pref string) int {
  	tree := newTrie()
  	for _, w := range words {
  		tree.insert(w)
  	}
  	return tree.search(pref)
  }
  

All Problems

All Solutions