经典算法面试题目-判断两个字符串是否是变位词(1.4)
发布日期:2021-06-29 13:36:58
浏览次数:2
分类:技术文章
本文共 1717 字,大约阅读时间需要 5 分钟。
题目
Write a method to decide if two strings are anagrams or not.
写一个函数判断两个字符串是否是变位词。
解答
变位词(anagrams)指的是组成两个单词的字符相同,但位置不同的单词。
比如说, abbcd和abcdb就是一对变位词。
也就是说,2个字符串,不管排列顺序如何,只要全部的单个字符能对应上,就是一对变位词!该题目有两种做法:
时间复杂度为O(nlogn)的解法
由于组成变位词的字符是一模一样的,所以按照字典序排序后,两个字符串也就相等了。 因此我们可以用O(nlogn)的时间去排序,然后用O(n)的时间比较它们是否相等即可。
代码如下:
//需要头文件#includebool isAnagram1(string s, string t){ if(s=="" || t=="") return false; if(s.length() != t.length()) return false; //sort(s,s+s.length);//如果s是字符数组,就这样调用 sort(&s[0], &s[0]+s.length()); sort(&t[0], &t[0]+t.length()); if(s == t) return true; else return false;}
时间复杂度为O(n)的解法
由于组成变位词的字符是一模一样的, 因此我们可以先统计每个字符串中各个字符出现的次数, 然后看这两个字符串中各字符出现次数是否一样。如果是,则它们是一对变位词。 这需要开一个辅助数组来保存各字符的出现次数。我们可以开一个大小是256的整数数组(ascii码范围内的字符), 遍历第一个字符串时,将相应字符出现的次数加1;遍历第二个字符串时, 将相应字符出现的次数减1。最后如果数组中256个数都为0,说明两个字符串是一对变位词。 (第1个字符串中出现的字符都被第2个字符串出现的字符抵消了), 如果数组中有一个不为0,说明它们不是一对变位词。
代码如下:
//必须有头文件:#includebool isAnagram2(string s, string t){ if(s=="" || t=="") return false; if(s.length() != t.length()) return false; int len = s.length(); int c[256]; memset(c, 0, sizeof(c)); for(int i=0; i
全部代码:
#include#include //用sort函数必须加的头文件#include using namespace std;bool isAnagram1(string s, string t){ if(s=="" || t=="") return false; if(s.length() != t.length()) return false; //sort(s,s+s.length);//如果s是字符数组,就这样调用 sort(&s[0], &s[0]+s.length()); sort(&t[0], &t[0]+t.length()); if(s == t) return true; else return false;}bool isAnagram2(string s, string t){ if(s=="" || t=="") return false; if(s.length() != t.length()) return false; int len = s.length(); int c[256]; memset(c, 0, sizeof(c)); for(int i=0; i
转载地址:https://chenhx.blog.csdn.net/article/details/52005100 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月10日 03时51分20秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
领导让我整理上个季度的销售额,幸好我会Python数据分析,你猜我几点下班
2019-04-29
【Python爬虫实战】为何如此痴迷Python?还不是因为爱看小姐姐图
2019-04-29
2021年6月全国程序员薪资出炉,大佬您上榜了吗?
2019-04-29
零基础自学Python,你也可以实现经济独立!
2019-04-29
数字化转型的主干道上,华为云以“三大关键”成企业智能化推手
2019-04-29
数字化为何不走“捷”“径”?
2019-04-29
和总裁、专家交朋友,华为云助推政企智能化升级又做到前面去了
2019-04-29
BCOP章鱼船长,6月22日晚上8点上线薄饼
2019-04-29
为战疫助力,半导体功不可没
2019-04-29
了解这些操作,Python中99%的文件操作都将变得游刃有余!
2019-04-29
知道如何操作还不够!深入了解4大热门机器学习算法
2019-04-29
只有经历过,才能深刻理解的9个编程道理
2019-04-29
发现超能力:这些数据科学技能助你更高效专业
2019-04-29
AI当道,人工智能将如何改变金融业?
2019-04-29
消除性别成见,技术领域需要更多“乘风破浪的姐姐”
2019-04-29
7行代码击败整个金融业,这对20多岁的爱尔兰兄弟是如何做到的?
2019-04-29
2020十大编程博客:私藏的宝藏编程语言博客大放送!
2019-04-29
编程中的角色选择:哪类工作角色最适合你?
2019-04-29
10种算法一文打尽!基本图表算法的视觉化阐释
2019-04-29