首页 > 代码库 > 变位词

变位词

题目描述:
如果两个字符串的字符一样,但是顺序不一样,被认为是兄弟字符串,比如bad和adb即为兄弟字符串,现提供一个字符串,如何在字典中迅速找到它的兄弟字符串,请描述数据结构和查询过程。
思路一:用计数排序
设计一个数组,对单词每个字母计数加1,对兄弟单词每个字母计数减去1,如果最后这个数组的计数是0,那么就为兄弟单词

bool isBrotherWord(string &str1, string &str2)
{
    int len1 = str1.length();
    int len2 = str2.length();
    //长度不相等,肯定不是兄弟单词
    if(len1 != len2)
        return false;

    //设计一个数组,并且初始化为0
    int a[26] = {0};

    //计数
    for(int i = 0;i < len1; i++)
    {
        a[str1[i] - ‘A‘]++;
        a[str2[i] - ‘A‘]--;
    }

    //如果最后计数不为0,那么就不为兄弟单词
    for(int i = 0; i < len1; i++)
    {
        if(a[str1[i] - ‘A‘] != 0)
            return false;
    }
    return true;
}

思路二:哈希表
①先创建哈希表,统计字符串1中出现的次数;
②将哈希表扫描第二个字符串时,扫描到每个字符时候,为哈希表减去1,
③如果最后哈希表所有的值都为0,则为变位词,否则不是变位词

bool isBrotherWord(char *str1, char *str2) 
{ 
    //输入不合法 
    if(str1 == NULL || str2 == NULL) 
        return 0; 
    //创建哈希表,并且初始化哈希表 
    const int tableSize = 256; 
    unsigned int hashTable[tableSize]; 
    for(int i = 0;i<tableSize;i++) 
        hashTable[i] = 0; 
    char *pHashKey = str1; 
    while(*pHashKey) 
    { 
        hashTable[*pHashKey]++; 
        pHashKey ++; 

    } 
    char *pHashKey1 = str2; 
    while(*pHashKey1) 
    { 
        hashTable[*pHaKey1]--; 
        pHashKey1 ++; 

    } 
    if(hashTable[*pHashKey1] == 0) 
        return true;
    return false;
}

思路三:使用哈希表和链表
①将单词按字母从小到大的顺序重新排序后作为其key,使用链表将所有兄弟单词串在一起hash_map的key为单词的key,value为链表的起始地址。
②遍历字典,将每个单词都按照key加入到对应的链表中,当需要找兄弟单词时候,只需要取这个单词的key,之后到hash_map中找到对应的链表即可。
创建哈希表时间复杂度为O(n),查找兄弟单词时间复杂度为O(1)
思路四:使用哈希表和链表

①将每个字母对应一个质数,之后让对应的质数相乘,将得到的值放入哈希表中作为key
②使用链表将所有兄弟单词串在一起
③用户输入单词,我们之间遍历哈希表,将链表遍历输出得到所有的兄弟单词。
创建哈希表时间复杂度为O(n),查找兄弟单词时间复杂度为O(1)
思路四:使用trie树

在字典树前缀中再存储一个vector结构的容器

struct word
{
    vector<string> brother;//用于保存每个单词的兄弟单词
    word *next[26]; //字典树中每个节点代表一个字符,并指向下一个字符
};

首先根据字典中的单词来建立字典树,建立的时候,需要稍微特殊处理一下,就是比如pots、stop和tops互为兄弟单词,那么在字典中按照首字母顺序的话,应该先遇到pots单词,那么我首先对其进行排序,结果是opts,那么字典树中就分别建立4个节点,分别为o->p->t->s,当然这个是不同层次的,在节点s处的vector容器brother中添加单词pots,遇到stop的时候,同样的方法,排序是opts,此时发现这4个节点已经建立了,那么只需要在第四个节点s处的vector容器brother中添加单词stop,tops单词的处理方法是同样的。
这样建立完字典树后,查询兄弟单词的效率就会很高了,比哈希的效率还要高;查到tops的兄弟的单词的时候,首先排序,那么就是opts,然后在字典树中查找opts,在s处将其vector容器brother中的的单词输出就是tops的所有兄弟单词。
这种方法理解需要以后补充