[2185] LeetCode 刷题笔记： 统计包含给定前缀的字符串 [s]
目录题目描述
给你一个字符串数组 words 和一个字符串 pref 。
返回 words 中以 pref 作为 前缀 的字符串的数目。
字符串 s 的 前缀 就是 s 的任一前导连续字符串。
题解参考
简单模拟
按照题意，对 words 每个单词进行判断，是否以 pref 开头即可。最后返回满足条件的单词的数量。
Algorithm [ 统计包含给定前缀的字符串: 简单模拟 ]
Input: { words /* array of string */, pref /* string */ }
Output: { 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. */
Function SimulationMethod
count <- 0 // the number of strings in words that contain pref as a prefix.
For word iter words do
If word.size < pref.size
Continue
EndIf
flag <- False
For i <- 0 to pref.size
If pref[i] != word[i]
flag <- true
Break
EndIf
EndFor
EndFor
Return count
EndFunction
复杂度分析
-
时间复杂度：\(O(n \times m)\)，其中 \(n\) 是输入
words的长度，m是输入pref的长度。 -
空间复杂度：\(O(1)\)，仅需要常数空间。
参考题解
C/C++ 的相关参考
C/C++ 的相关参考
class Solution {
struct Simulation {};
public:
int prefixCountImpl(Simulation, vector<string>& words, string pref) {
int res = 0;
for (string& word : words) {
// if (word.compare(0, pref.size(), pref) == 0) {
// res++;
// }
if( word.size() < pref.size() ) continue;
bool flag = false;
for(int i = 0; i < pref.size(); ++i) {
if(pref[i] != word[i]) {
flag=true;
break;
}
}
if(!flag) res++;
}
return res;
}
int prefixCount(vector<string>& words, string pref) {
return prefixCountImpl(Simulation(), words, pref);
}
};
Rust 的相关参考
Rust 的相关参考
impl Simulation for Solution {}
trait Simulation {
fn prefix_count(words: Vec<String>, pref: String) -> i32 {
// words.iter().fold(0, |cnt, word| if word.starts_with(&pref) { cnt + 1 } else { cnt })
words.iter().fold(0,|acc, str| if str.starts_with(&pref) { acc+1 } else { acc })
}
}