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

【题目】

原文:

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

译文:

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

【分析】

变位词(anagrams)指的是组成两个单词的字符相同,但位置不同的单词。比如说, abbcd和abcdb就是一对变位词。该题目有两种思路:

【思路一】

由于变位词只是字母的顺序改变,字符长度,字符种类没有改变,所以根据此我们只要重新根据字典序排序一下,两个字符串也就一样了。

The eyes(眼睛)——They see.(它们看得见。)这是一对变位词。

根据字典序排序他们都会变成:eeehtsy

时间复杂度为:O(nlogn)

【思路二】

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

【代码一】

/*********************************
*   日期:2014-05-06
*   作者:SJF0115
*   题目: 判断字符串是否为变位词
*   来源:CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

//判断字符串是否为变位词
bool IsAnagrams(string str1,string str2){
    if(str1 == "" || str2 == ""){
        return false;
    }
    int len1 = str1.length();
    int len2 = str2.length();
    //变位词长度一样
    if(len1 != len2){
        return false;
    }
    //排序
    sort(&str1[0],&str1[0]+len1);
    sort(&str2[0],&str2[0]+len2);
    if(str1 == str2){
        return true;
    }
    else{
        return false;
    }
}

int main(){
    char str1[] = "the eyes";
    char str2[] = "they see";
    bool result = IsAnagrams(str1,str2);
    cout<<result<<endl;
    return 0;
}

【代码二】

//判断字符串是否为变位词
bool IsAnagrams(string str1,string str2){
    int i;
    if(str1 == "" || str2 == ""){
        return false;
    }
    int len1 = str1.length();
    int len2 = str2.length();
    //变位词长度一样
    if(len1 != len2){
        return false;
    }
    //初始化
    int vis[256];
    memset(vis,0,sizeof(vis));
    //遍历第一个字符串,将相应字符出现的次数加1
    //遍历第二个字符串,将相应字符出现的次数减1
    for(i = 0;i < len1;i++){
        vis[str1[i]] ++;
        vis[str2[i]] --;
    }
    //判断是否为变位词 如果数组中256个数都为0,说明两个字符串是一对变位词。
    for(i = 0;i < 256;i++){
        if(vis[i] != 0){
            return false;
        }
    }
    return true;
}
时间: 2024-11-15 09:36:40

CareerCup之1.4判断字符串是否为变位词的相关文章

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

题目 Write a method to decide if two strings are anagrams or not. 写一个函数判断两个字符串是否是变位词. 解答 变位词(anagrams)指的是组成两个单词的字符相同,但位置不同的单词. 比如说, abbcd和abcdb就是一对变位词. 也就是说,2个字符串,不管排列顺序如何,只要全部的单个字符能对应上,就是一对变位词! 该题目有两种做法: 时间复杂度为O(nlogn)的解法 由于组成变位词的字符是一模一样的,所以按照字典序排序后,两

python判断字符串是否包含子字符串的方法

 这篇文章主要介绍了python判断字符串是否包含子字符串的方法,实例分析了Python中的in与find方法来实现这一功能,非常具有实用价值,需要的朋友可以参考下     本文实例讲述了python判断字符串是否包含子字符串的方法.分享给大家供大家参考.具体如下: python的string对象没有contains方法,不用使用string.contains的方法判断是否包含子字符串,但是python有更简单的方法来替换contains函数. 方法1:使用 in 方法实现contains的功能

js 判断字符串长度:计算字符串长度/判断空

计算字符串长度可用的三种方法:   echo "$str"awk '{print length($0)}'  expr length "$str"  echo "$str"wc -c  但是第三种得出的值会多1,可能是把结束符也计算在内了. 判断字符串为空的方法有三种:   if [ "$str" = "" ]  if [ x"$str" = x ]  if [ -z "$st

判断字符串emailAddr是否为合法的email格式

字符串 /** * 判断字符串emailAddr是否为合法的email格式 * 主要判断'@'及'.'是否出现,以及两者的位置 * @param emailAddr 输入的email地址 * @return true/false. */ function emailCheck(emailAddr){    if((emailAddr == null) || (emailAddr.length < 2)) return false ;     // 需出现'@',且不在首字符.    var aP

C#中如何判断字符串是否可以转化为数字

/// <summary> /// 判断字符串是否可以转化为数字 /// </summary> /// <param name="str">要检查的字符串</param> /// <returns>true:可以转换为数字:false:不是数字</returns> public static bool IsNumberic(string str) { double vsNum; bool isNum; isNum

JavaScript如何判断字符串长度(英文占1个字符,中文汉字占2个字符)

//计算字符串长度(英文占1个字符,中文汉字占2个字符) 方法一: String.prototype.gblen = function() { var len = 0; for (var i=0; i<this.length; i++) { if (this.charCodeAt(i)>127 || this.charCodeAt(i)==94) { len += 2; } else { len ++; } } return len; } 方法二: function strlen(str){

C#判断字符串是否为日期格式

判断字符串是否为时期格式时,可以使用正则表达式.验证日期格式的正则表达式主要有以下3种: \b(?<year>\d{2,4})/(?<month>\d{1,2})/(?<day>\d{1,2})\b 或 \b(?<year>\d{2,4})-(?<month>\d{1,2})-(?<day>\d{1,2})\b 或 \b(?<year>\d{2,4})年(?<month>\d{1,2})月(?<day&g

判断字符串中相同字符的个数

判断字符串中相同字符的个数  =============================  函 数 名:GetCount  作    用:判断字符串中相同字符的个数  参    数:  ==============================  Private Function GetCount(Strs,Word)   Dim N1,N2,N3   N1=Len(Strs)   N2=Len(Replace(Strs,Word,""))   N3=Len(Word)   GetC

Shell中判断字符串是否为数字的6种方法分享

  本篇文章主要介绍了"shell 判断字符串是否为数字",主要涉及到shell 判断字符串是否为数字方面的内容,对于shell 判断字符串是否为数字感兴趣的同学可以参考一下. ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #!/bin/bash   ## 方法