力扣290单词规律

直接上题目
给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true
示例 2:

输入:pattern = "abba", s = "dog cat cat fish"
输出: false
示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

很简单，和上一道题类似，但是上一个一维数组解决但是这个得二维数组
我先直接上代码

bool wordPattern(char * pattern, char * s){
    char a[301][3001];
    char *p=strtok(s," ");
    int pos=0,len=strlen(pattern);
    while(p!=NULL)
    {
        sprintf(a[pos++],"%s",p);
        p=strtok(NULL," ");
    }
    if(len!=pos)
        return false;
    for(int i = 0 ; i < len; i++)
        for(int j = i + 1; j < len; j++)
        {
            int re = strcmp(a[i],a[j]);
            if((pattern[i] == pattern[j] && re != 0) ||
                (pattern[i] != pattern[j] && re == 0)
            )
                return false;
        }
    return true;
}

道理和昨天的是一样的。

当然也可以用哈希算法，我没有去写，但是思路还是很好理解的，我先贴上大佬的代码，后期去研究研究怎么写的

struct Hash_Table{
    int key;//键
    char val[30];//把s中单个的字符串例如dog拷贝到这个哈希表中，这个30和提供的测试数据有关，测试过，数据中s中单个字符串不大于30
    UT_hash_handle hh;
};

bool wordPattern(char * pattern, char * s){
    char** array = malloc(sizeof(char*)*300);//定义一个二维数组（二级指针），其数组是一级指针，也就是一维数组，指向s中单独的字符串，例如dog，1 <= pattern.length <= 300，所以为包含300个一级指针类型的二级指针开辟内存，当然也有可能s中字符串的个数大于pattern.length，还是跟提供测试数据有关，300通过的了测试
    int count = 0;//记录s包含的以空格分隔的字符串的个数，例如dog cat则cout=2
    array[count] = strtok(s," ");//字符串分隔函数的用法就是如此
    for(count = 0; array[count]!=NULL;){//字符串分隔函数的用法就是如此
        array[++count] = strtok(NULL," ");//字符串分隔函数的用法就是如此
    }//自此，array内包含cout个字符串，指向每个字符串的指针对应于array[i]
    if(count != strlen(pattern)){//判断pattern字符个数和s中以空格分隔的字符串个数是否相等
        return false;//例如pattern = "ab", s = "dog cat cat", 2!=3，直接返回false
    }

    struct Hash_Table* table1 = NULL;//记录pattern到s的映射
    struct Hash_Table* table2 = NULL;//记录s到pattern的映射
    struct Hash_Table* temp = NULL;//用于存储数据加入哈希表
    int patternnumber[300] = {0};//把pattern中的单个字符转换为int型，好处理

    for(int i=0; i<strlen(pattern); i++){
        patternnumber[i] = pattern[i]-'a';//把pattern中的单个字符转换为int型，好处理
        HASH_FIND_INT(table1,&(patternnumber[i]),temp);//查找patternnumber[i])是否在哈希表table1出现，返回结果在temp中
        if(temp == NULL){//如果不存在
            temp = malloc(sizeof(struct Hash_Table));//为temp开辟内存
            temp->key = patternnumber[i];//将数据存储到temp结构体中，patternnumber[i]为键
            strcpy(temp->val,array[i]);//将s中的以空格分隔的字符串拷贝到结构体val中，作为值
            HASH_ADD_INT(table1,key,temp);//key为键，也就是通过哈希函数把key转换为地址，将结构体存到该地址。完成添加add，前面key赋值的是patternnumber[i]，所以patternnumber[i]是用来查找的键，可以得到的是值val，即array[i]
        }
        else if(strcmp(temp->val,array[i])!=0)
            return false;//当查到不是第一次出现的元素，比较之前映射的array[i]和现在的array[i]，不一样直接false
    }

    for(int i=0; i<count; i++){//与哈希表1类似，只不过存储s到pattern的映射关系
        HASH_FIND_STR(table2,array[i],temp);
        if(temp == NULL){
            temp = malloc(sizeof(struct Hash_Table));
            temp->key = patternnumber[i];
            strcpy(temp->val,array[i]);
            HASH_ADD_STR(table2,val,temp);//注意这里的第二个参数键的名字是val，在哈希表table2中，我们是通过键(key)s的字符也就是array[i]中指向的字符，来得到val即pattenumber，所以下面if中要判断，当不是第一次出现的字符时，对应的之前的映射pattenumber和现在的pattenumber是否一样，不一样直接false
        }
        else if(temp->key!=patternnumber[i])
            return false;
    }  
    return true;//前面所有false情况排除，那就符合题意，返回true
    

}

这里需要注意的一点知识点就是，一个是用到了二维数组，还有一个就是用到了切割字符串的办法，strtok() 此时要传入要切割的函数以及哪个位置要进行切割，这点需要牢记。
最后就是写逻辑判断的时候思路要清晰的哦

力扣290单词规律

评论 (0)