c++ - 从字符串向量中获取字符
问题描述
我有一个字符串向量,并尝试使用两个循环到达每个单词的每个字符,如下所示。有没有办法不使用两个循环,所以我不会超过 O(n) 时间复杂度。
澄清:我想要做的是将字母转换为电话键盘中的数字,然后搜索这些数字(如果它们在 phoneNumber 字符串中可用)。
#include<bits/stdc++.h>
using namespace std;
// vector<string> words={"foo","bar","car","cat","lawyer"};
// string phoneNumber="3226773664"
void lookup(vector<string> &words,string phoneNumber){
string strtonumber="";
int ascii;
for(auto word:words ){
strtonumber="";
for(auto chr:word ){
ascii=int(chr);
if(ascii >= 97 && ascii<=99)
strtonumber+="2";
if(ascii >= 100 && ascii<=102)
strtonumber+="3";
if(ascii >= 103 && ascii<=105)
strtonumber+="4";
if(ascii >= 106 && ascii<=108)
strtonumber+="5";
if(ascii >= 109 && ascii<=111)
strtonumber+="6";
if(ascii >= 112 && ascii<=115)
strtonumber+="7";
if(ascii >= 116 && ascii<=118)
strtonumber+="8";
if(ascii >= 119 && ascii<=122)
strtonumber+="9";
}
if (phoneNumber.find(strtonumber) != string::npos)
cout<<"Numerical version of these words available in your Phone Number string"<<endl;
}
解决方案
有没有办法不使用两个循环,所以我不会超过 O(n) 时间复杂度。
嵌套循环并不总是O(N^2)
。或者更准确地说:big-O 仅在您说出实际情况时才有意义N
。这个循环很复杂O(N^2)
:
for (unsigned i=0; i < N; ++i) {
for (unsigned j=0; j < N; ++j) {
foo(i,j); // <- this is called N*N times
}
}
但是,您的循环与
for (unsigned i=0; i < number_of_strings; ++i) {
for (unsigned j=0; j < number_of_characters(i); ++j) {
foo( words[i][j] );
}
}
并且只是您要处理的字符数O( number_of_strings * number_of_characters )
是什么O(N)
时候。N
考虑它的另一种方法是考虑如果对字符串执行相同的操作,复杂性会发生哪些变化"foobarcarcatlawyer"
。没有什么。如果您迭代此字符串,则转换单个字符的次数保持完全相同。
您不能处理N
小于 的字符O(N)
。
推荐阅读
- python - 在 MoviePy 中的视频上叠加视频
- windows - WinDbg 未加载内核驱动程序的符号
- javascript - TinyMCE 将 base64 图像转换为 blob 对象
- ruby-on-rails - 使用 posgis 适配器在 st_distance 和几何中面临问题
- unix - 如何使用 awk 替换二进制文件中的单个字节
- android - 对设备中的文档(.pdf、.doc、.xlsx)进行本机搜索
- amazon-web-services - AWS Glue - 条件触发器是否可以根据另一个工作流程中的作业条件触发?
- javascript - 动画 CSS 不随页面漫步
- excel - 数据工厂中具有多行列标题和空白列的 Excel 文件?
- reactjs - 如何使用 Next.js 访问当前在导航中加载的 url 或页面