经典算法面试题目-判断两个字符串是否是变位词(1.4)

题目

Write a method to decide if two strings are anagrams or not.

写一个函数判断两个字符串是否是变位词。

解答

变位词(anagrams)指的是组成两个单词的字符相同,但位置不同的单词。

比如说, abbcd和abcdb就是一对变位词。
也就是说,2个字符串,不管排列顺序如何,只要全部的单个字符能对应上,就是一对变位词!

该题目有两种做法:

时间复杂度为O(nlogn)的解法

由于组成变位词的字符是一模一样的,所以按照字典序排序后,两个字符串也就相等了。 因此我们可以用O(nlogn)的时间去排序,然后用O(n)的时间比较它们是否相等即可。

代码如下:

//需要头文件#include<algorithm>

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

时间复杂度为O(n)的解法

由于组成变位词的字符是一模一样的, 因此我们可以先统计每个字符串中各个字符出现的次数, 然后看这两个字符串中各字符出现次数是否一样。如果是,则它们是一对变位词。 这需要开一个辅助数组来保存各字符的出现次数。我们可以开一个大小是256的整数数组(ascii码范围内的字符), 遍历第一个字符串时,将相应字符出现的次数加1;遍历第二个字符串时, 将相应字符出现的次数减1。最后如果数组中256个数都为0,说明两个字符串是一对变位词。 (第1个字符串中出现的字符都被第2个字符串出现的字符抵消了), 如果数组中有一个不为0,说明它们不是一对变位词。

代码如下:

//必须有头文件:#include <cstring>

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<len; ++i){
        ++c[(int)s[i]];
        --c[(int)t[i]];
    }

    for(int i=0; i<256; ++i)
        if(c[i] != 0)
            return false;
    return true;
}

全部代码:

#include <iostream>
#include <algorithm>//用sort函数必须加的头文件
#include <cstring>
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<len; ++i){
        ++c[(int)s[i]];
        --c[(int)t[i]];
    }

    for(int i=0; i<256; ++i)
        if(c[i] != 0)
            return false;
    return true;
}

int main()
{
    string s="asdfghj";
    string t="jhgfdsa";
    bool bo = isAnagram1(s,t);
    cout<<bo<<endl;//输出结果为1

    s="asdfghj";
    t="jhgfdss";
    bo = isAnagram1(s,t);
    cout<<bo<<endl;//输出结果为0

    s="asdfghj";
    t="jhgfdsa";
    bo = isAnagram2(s,t);
    cout<<bo<<endl;//输出结果为1

    s="asdfghj";
    t="jhgfdss";
    bo = isAnagram2(s,t);
    cout<<bo<<endl;//输出结果为0
    return 0;
}
时间: 2024-12-24 21:28:19

经典算法面试题目-判断两个字符串是否是变位词(1.4)的相关文章

经典算法面试题目-判断一个字符串中的字符是否唯一(1.1)

题目: Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures? 实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构. (即只使用基本的数据结构) 解答: 首先,你可以问面试官,构成字符串的字符集有多大?是ASCII字符,还是只是26个字母? 还是有更大的字符集,对于不同

经典算法面试题目-判断s2是否是s1的旋转字符串(1.8)

题目 Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring ( i.e., "waterbottle" is a rotation of &qu

经典算法面试题目-设计算法移除字符串中重复的字符(1.3)

题目 Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not. FOLLOW UP Write the test cases for this metho

经典算法面试题目-翻转一个C风格的字符串(1.2)

题目: Write code to reverse a C-Style String. (C-String means that "abcd" is represented as five characters, including the null character.) 写代码翻转一个C风格的字符串.(C风格的意思是"abcd"需要用5个字符来表示,包含末尾的 结束字符) 解答: 这道题如果就是要考察你有没有注意到C风格字符串最后的那个结束符,那我觉得还是像书

经典算法面试题目-置矩阵行列元素为0(1.7)

题目 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0. 写一个函数处理一个MxN的矩阵,如果矩阵中某个元素为0,那么把它所在的行和列都置为0. 解答 简单题.遍历一次矩阵,当遇到元素等于0时,记录下这个元素对应的行和列. 可以开一个行数组row和列数组col,当元素a[i][j]等于0时, 就把row[i]和col[j]置为1. 第二次遍

经典算法面试题目-矩阵旋转90度(1.6)

题目 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? 一张图像表示成NxN的矩阵,图像中每个像素是4个字节,写一个函数把图像旋转90度. 你能原地进行操作吗?(即不开辟额外的存储空间) 解答 我们假设要将图像逆时针旋转90

CareerCup之1.4判断字符串是否为变位词

[题目] 原文: 1.4 Write a method to decide if two strings are anagrams or not. 译文: 写一个函数判断两个字符串是否是变位词. [分析] 变位词(anagrams)指的是组成两个单词的字符相同,但位置不同的单词.比如说, abbcd和abcdb就是一对变位词.该题目有两种思路: [思路一] 由于变位词只是字母的顺序改变,字符长度,字符种类没有改变,所以根据此我们只要重新根据字典序排序一下,两个字符串也就一样了. The eyes

怎样判断两个字符串“内容”相等

问题描述 怎样判断两个字符串内容相等如,目前有两个字符串"dog,cat","cat,dog"我希望通过比较知道它们从内容上是相等的(都是包含dog和cat两个动物),不知道有什么比较好的方法.谢谢大家 解决方案 解决方案二:很简单啊,用split分开,然后排序,然后逐个比较就可以了解决方案三:@_@解决方案四:用split进行分开,然后用for循环进行判断里面的项是否一样就可以了解决方案五:用split()分开,放到两个字符串数组里,然后对这两个数组进行处理就可以

php简单判断两个字符串是否相等的方法_php技巧

本文实例讲述了php简单判断两个字符串是否相等的方法.分享给大家供大家参考.具体实现方法如下: <?php function strcomp($str1,$str2){ if($str1 == $str2){ return TRUE; }else{ return FALSE; } } echo strcomp("First string","Second string"); //Returns FALSE echo strcomp("A string