Problem 10393 The One-Handed Typist，能打的單字

吉米手指受傷了，但他為了向老闆證明他可以打長單字( 因為老闆認為長的單字會使人看起來更聰明 )，現在有一列字串可以添加到老闆的文件，使老闆覺得他更聰明，你必需要幫他找出他「可以打」以及「最長」的字，如果「最長」的字有很多，依照字母大到小排列。

首先宣告幾個結構( struct )以及結構陣列還有函式來開啟或關閉吉米能打的字，C 語言程式碼如下：

struct finger
{
    char word;
    int fId;
    int isUse;   
};

struct string
{
    char str[51];    
};

struct string s, sArray[1000];
struct finger f[32];
int index, maxLen;

void creat()
{
    f[0].word = 'a', f[0].fId = 1, f[1].word = 'b', f[1].fId = 4;
    f[2].word = 'c', f[2].fId = 3, f[3].word = 'd', f[3].fId = 3;
    f[4].word = 'e', f[4].fId = 3, f[5].word = 'f', f[5].fId = 4;
    f[6].word = 'g', f[6].fId = 4, f[7].word = 'h', f[7].fId = 7;
    f[8].word = 'i', f[8].fId = 8, f[9].word = 'j', f[9].fId = 7;
    f[10].word = 'k', f[10].fId = 8, f[11].word = 'l', f[11].fId = 9;
    f[12].word = 'm', f[12].fId = 7, f[13].word = 'n', f[13].fId = 7;
    f[14].word = 'o', f[14].fId = 9, f[15].word = 'p', f[15].fId = 10;
    f[16].word = 'q', f[16].fId = 1, f[17].word = 'r', f[17].fId = 4;
    f[18].word = 's', f[18].fId = 2, f[19].word = 't', f[19].fId = 4;
    f[20].word = 'u', f[20].fId = 7, f[21].word = 'v', f[21].fId = 4;
    f[22].word = 'w', f[22].fId = 2, f[23].word = 'x', f[23].fId = 2;
    f[24].word = 'y', f[24].fId = 7, f[25].word = 'z', f[25].fId = 1;
    f[26].word = ' ', f[26].fId = 5, f[27].word = ' ', f[27].fId = 6;
    f[28].word = ',', f[28].fId = 8, f[29].word = '.', f[29].fId = 9;
    f[30].word = ';', f[30].fId = 10, f[31].word = '/', f[31].fId = 10;
}

void allUseFinger()
{
    int i;
    for (i = 0; i < 32; i ++)
        f[i].isUse = 1;
}

void notUseFinger(int n)
{
    if (n == 1) { f[0].isUse = 0, f[16].isUse = 0, f[25].isUse = 0; return; }
    if (n == 2) { f[18].isUse = 0, f[22].isUse = 0, f[23].isUse = 0; return; }
    if (n == 3) { f[2].isUse = 0, f[3].isUse = 0, f[4].isUse = 0; return; }
    if (n == 4) 
    { f[1].isUse = 0, f[5].isUse = 0, f[6].isUse = 0, f[17].isUse = 0, f[19].isUse = 0, f[21].isUse = 0; return; }
    if (n == 5) { f[26].isUse = 0; return; }
    if (n == 6) { f[27].isUse = 0; return; }
    if (n == 7) 
    { f[7].isUse = 0, f[9].isUse = 0, f[12].isUse = 0, f[13].isUse = 0, f[20].isUse = 0, f[24].isUse = 0; return; }
    if (n == 8) { f[8].isUse = 0, f[10].isUse = 0, f[28].isUse = 0; return; }
    if (n == 9) { f[11].isUse = 0, f[14].isUse = 0, f[29].isUse = 0; return; }
    if (n == 10) { f[15].isUse = 0, f[30].isUse = 0, f[31].isUse = 0; return; }
}

int isUseWord(char ch)
{
    if (ch == ' ') return (f[25].isUse || f[26].isUse); 
    if (ch == ',') return f[28].isUse;
    if (ch == '.') return f[29].isUse;
    if (ch == ';') return f[30].isUse;
    if (ch == '/') return f[31].isUse;
    int n = ch - 'a';
    return f[n].isUse;
}

在主程式只須這樣呼叫：

creat();
index = 0, maxLen = 0;  
allUseFinger();  
while (F --)
    scanf("%d", &nUF), notUseFinger(nUF);

再來就是讀入一列的添加字串，每讀入一個就判斷吉米是否能打出這個字，以及字串的長度。如果可以打，就判斷它的長度是否大於目前的最大長度？大於，則將索引歸 0，最大長度改為此字串長度，再將此字加入陣列；等於，則加入此字到陣列內，順便排序比較；小於，則剔除。加入到陣列的函式 C 語言程式碼如下：

void insert()
{
    int repeatIndex = 0, i;
    for (i = 0; i < index ; i ++)
    {
        if (strcmp(s.str, sArray[i].str) == 0)
           return;
    }       
    struct string repeatS;
    strcpy(sArray[index ++].str, s.str); 
    for (i = index - 1; i >= 1; i ++)
    {
        if (strcmp(sArray[i].str, sArray[i - 1].str) == -1)
        {
            strcpy(repeatS.str, sArray[i].str);
            strcpy(sArray[i].str, sArray[i - 1].str);
            strcpy(sArray[i - 1].str, repeatS.str);
        }
        else return;
    }
    
    return;
}

最後，主程式只須這樣呼叫：

while (N --)
{
    scanf("%s", s.str);
    isKey = 1;
    len = strlen(s.str);
    for (i = 0; s.str[i]; i ++)
    {
        if (!isUseWord(s.str[i]))
        {
            isKey = 0;
            break;
        }
    }
    if (isKey && maxLen < len) maxLen = len, index = 0;
    if (isKey && maxLen == len) insert();     
}
printf("%d\n", index);
for (i = 0; i < index; i ++)
    printf("%s\n", sArray[i].str);

By David.K

p10393題目連結
回ACM題庫目錄
回首頁