Question

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

Solution 1

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

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;
  }
};

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
  }
}

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;
}

Solution 2

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)

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);
  }
};

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)
}