LeetCode 75 Level 1 - Day 12 Sliding Window/Two Pointer

438. Find All Anagrams in a String

• 題目連結
• 難易度：Medium

題目敘述

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

預設函數

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findAnagrams(char * s, char * p, int* returnSize){

}

題目限制

• <= s.length, p.length <=
• s and p consist of lowercase English letters.

解題過程及程式碼

本題給2個字串 s 和 p，需要輸出在 s 之中，有存在 p 的易位構詞的位置，所謂的易位構詞由維基百科來說「是將組成一個詞或短句的字母重新排列順序，原文中所有字母的每次出現都被使用一次，這樣構造出另外一些新的詞或短句。」

• 簡單例子請見如下圖 (來源：維基百科)，[l, i, s, t, e, n]經由將字母的重組可以得到[s, i, l, e, n, t]。

  

• 複雜一點的例子，如輸入 s = "cbaebabacd", p = "abc"，從 0 的位置可以取得字串"cba"，它就是"abc"的易位構詞，在 6 的位置可以取"bac"也是"abc"的易位構詞。

解題想法是用來2個指針作為一個視窗來檢查s[i]中是否有p[i]的易位構詞，從s[i]最左邊開始往右邊檢查，檢查的方法就是兩個易位構詞中字母出現數量是相同的，題目限制字母都是小寫，只要比較a~z的字母數量就可以知道是否為易位構詞。

• 程式碼上傳

#define MAX_ARRAY_SIZE 30000

int* findAnagrams(char * s, char * p, int* returnSize){
    /* 回傳易位構詞的位置是一個陣列，要建立動態記憶體 */
    int *ptr = (int *)malloc(sizeof(int) * MAX_ARRAY_SIZE);
    int p_char_array[26] = {0};
    int s_char_array[26] = {0};
    int i, s_num, p_num, counter;
    int ptr1, ptr2;

    i = 0;
    while (s[i] != '\0') {
        i++;
    }
    s_num = i;  /* 取得s的長度 */

    i = 0;
    while (p[i] != '\0') {
        p_char_array[p[i] - 'a'] += 1;  /* 找出p字母出現的次數 */
        i++;
    }
    p_num = i;  /* 取得p的長度 */

    /* 如果p比s長，根本無法從s中找出p的易位構詞 */
    if (p_num > s_num) {
        *returnSize = 0;
        return NULL;
    }

    /* 兩個指標起始點 */
    ptr1 = 0;
    ptr2 = p_num-1;
    counter = 0;  /* 計算找到幾個位置的易位構詞 */
    while (s[ptr2] != '\0') {
        /* 計算視窗內的字母出現次數 -> s_char_array[i] */
        if (ptr1 == 0) {
            for (int j=ptr1; j<=ptr2; j++) {
                s_char_array[s[j] - 'a'] += 1;
            }
        } else {
            s_char_array[s[ptr1 - 1] - 'a'] -= 1;
            s_char_array[s[ptr2] - 'a'] += 1;
        }

        /* 檢查s_char_array[i]和p_char_array[i]從a~z出現次數使否相同 -> 易位構詞 */
        int flag = 0;
        for (int k=0; k<26; k++) {
            if (p_char_array[k] != s_char_array[k]) {
                flag = 1;
                break;
            }
        }
        
        /* 把找到的易位構詞位置丟到陣列裡 */
        if (flag == 0) {
            ptr[counter] = ptr1;
            counter++;
        }
        ptr1++;
        ptr2++;
    }

    *returnSize = counter;
    return ptr;
}

再一周邁向終點，加油!