首页 > 试题广场 >

找到字符串中的异位词

[编程题]找到字符串中的异位词
  • 热度指数:650 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定两个字符串 s 和 p ,请你找到 s 子数组中的全部 p 的异位词的起始点。异位词值可以通过重新排列字符顺序(或者不排列)而相等的词。
你可以以任意顺序返回

数据范围: s 和 p 的长度满足 ,字符串中仅包含小写英文字母
示例1

输入

"cabac","abc"

输出

[0,2]
示例2

输入

"ababab","ab"

输出

[0,1,2,3,4]
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @param p string字符串
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int isCongruent(char* s, char* c) {
    // write code here
    // if (strlen(s) != strlen(c))
    //     return -1;
    int* hash1 = (int*)calloc(26, sizeof(int));
    int* hash2 = (int*)calloc(26, sizeof(int));
    for (int i = 0; i < strlen(c); i++) {
        hash1[s[i] - 'a'] += 1;
        hash2[c[i] - 'a'] += 1;
    }
    //int count = 0;
    for (int j = 0; j < 26; j++) {

        if (hash1[j] != hash2[j])
            return -1;
        // if (hash1[j] != 0)
        //     count += 1;

    }
    return strlen(s);
}
int* findWord(char* s, char* p, int* returnSize ) {
    // write code here
    int s_len = strlen(s);
    int p_len = strlen(p);
    printf("%d %d",s_len,p_len);
    int* ans = (int*)malloc(s_len*10* sizeof(int));
    int count=0;
    for (int i = 0; i + p_len <= s_len; i++) {
        // char *temp=(char *)malloc((p_len+10)*sizeof(char));
        // strncpy(temp,s+i,p_len);
        if(isCongruent(s+i,p)!=-1){
               ans[count++]=i;
        }
    }
    *returnSize=count;
    return ans;
}

发表于 2023-01-12 22:23:41 回复(0)