APCS 實作題 10610 第2題交錯字串參考解法

Originally published at https://yunlinsong.blogspot.com.

此題在高中生程式解題系統的題號為： c462: apcs 交錯字串 (Alternating Strings) 。

============底下文字取自 官方的試題文件============

問題描述
一個字串如果全由大寫英文字母組成，我們稱為大寫字串；如果全由小寫字母組成則稱為小寫字串。字串的長度是它所包含字母的個數，在本題中，字串均由大小寫英文字母組成。假設 k 是一個自然數，一個字串被稱為「k-交錯字串｣，如果它是由長度為 k 的大寫字串與長度為 k 的小寫字串交錯串接組成。

舉例來說，「StRiNg｣是一個 1-交錯字串，因為它是一個大寫一個小寫交替出現；而「heLLow｣是一個 2-交錯字串，因為它是兩個小寫接兩個大寫再接兩個小寫。但不管 k 是多少，「aBBaaa｣、「BaBaBB｣、「aaaAAbbCCCC｣都不是 k-交錯字串。

本題的目標是對於給定 k 值，在一個輸入字串找出最長一段連續子字串滿足 k-交錯字串的要求。例如 k=2 且輸入「aBBaaa｣，最長的 k-交錯字串是「BBaa｣，長度為 4。又如 k=1 且輸入「BaBaBB｣，最長的 k-交錯字串是「BaBaB｣，長度為 5。

============以上文字取自 官方的試題文件============

變數 preL 紀錄上一個字母的case是大寫u、小寫 l、未知n。

變數 curL 紀錄目前字母的case是大寫u、小寫 l、未知n。

將題目輸入的 k 值分成兩種情況來處理，這是因為筆者的解法在處理 k = 1 與 k > 1 這兩種情況時，剛好是相反的。

k = 1 時，當發生大小寫轉換(preL != curL)時，cg 就加 1；否則 cg 設為 1。 g 設為 max(g, cg)。

k > 1 時，請參考底下圖片：

當發生大小寫轉換(preL != curL)時，目前字母case累積次數 ck 會有三種情況：
ck < k，將 cg = 0。
ck == k，將 cg + k，cg = max(g, cg)。
ck > k，cg = k。

請注意到上圖右邊是個？號，這是因為在字串到尾端時，若沒有發生大小寫轉換，會少考慮到右邊的中 ck 次數的情況。

最大交錯字串長度(g)的改變會發生在紅色或橘色字母上。

目前交錯字串長度(cg)的改變會發生在橘色字母上。

C 程式碼：

#include <stdio.h>
#include <string.h>
#include <ctype.h>

// 回傳兩個整數的最大值
int max(int x,int y) {
    return (x >= y? x: y);
}

// 取得字母大小寫
char letterCase(char c)
{
    if(islower(c)) return 'l';
    if(isupper(c)) return 'u';
    return 'n';
}

int main(void) {
    int k;
    char str[100000];

    while(scanf("%d", &k) == 1)
    {
        int g = 0;      // 交錯字串最大長度
        int cg = 0;     // 目前交錯字串長度
        scanf("%s", str);
        int len = strlen(str);

        char preL = 'n';    // 上一個字母是大寫u、小寫 l、未知n。
        char curL;          // 目前字母是大寫u、小寫 l、未知n。
        int ck = 0;         // 目前字母case累積次數

        //  k 為 1 時要另外處理
        if(k == 1)
        {
            for(int i = 0; i < len; i++)
            {
                curL = letterCase(str[i]);      // 取得字母大小寫
                if(preL != curL)    // 轉換大小寫時
                    cg++;
                else                // 沒轉換大小寫時
                    cg = 1;

                g = max(cg, g);     // g 和 cg 誰是最大交錯字串長度
                preL = curL;        // 上一個字母case為目前字母case
            }
        }
        else
        {
            for(int i = 0; i < len; i++)
            {
                curL = letterCase(str[i]);

                if(preL == curL)
                {
                    ck++;
                    if(ck == k)             // 累積到 k 次
                    {
                        cg += k;            // 加到目前交錯字串長度
                        g = max(cg, g);     // g 和 cg 誰是最大交錯字串長度
                    }

                    if(ck > k)              // 目前case次數超過 k 次
                        cg = k;             // 目前交錯字串長度也只能等於 k
                }
                else if(preL != curL)       // 轉換大小寫時
                {
                    if(ck < k) cg = 0;      // 目前case次數小於 k 次，目前交錯字串長度歸零
                    ck = 1;                 // case次數從 1 開始
                }
                preL = curL;                // 上一個字母case為目前字母case
            }
        }

        printf("%d\n", g);
    }
    return 0;
}

C++ 程式碼：

Originally published at https://yunlinsong.blogspot.com.