計算機程式設計2 期末考的題目4

題目簡述

  • 輸入一個字串,包含大小寫及數字

    題目輸出

  • 每個字母可以是大寫或是小寫,從小到大輸出所有可能答案

範例

  • 輸入: b1H2e3

  • 輸出:
    b1h2e3
    b1h2E3
    b1H2e3
    b1H2E3
    B1h2e3
    B1h2E3
    B1H2e3
    B1H2E3

    解題想法

  • 這題其實是 Leetcode 784. Letter Case Permutation

  • 筆者想到了兩種實作方法

  • 第一種作法就是用遞迴跑出所有答案

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    /*****************************************
    Filename:cp2_final_p4_1.c
    Author:Willy Chen(willychen.org)
    Date:2018.08.14
    *****************************************/
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    /* 1:Uppercase 2:Lowercase */
    int upper(char c){
    if(c>='A'&&c<='Z')
    return 1;
    else
    return 2;
    }
    void dfs(char* input,int now,int len){
    if(now>=len){
    /* Print the answer */
    printf("%s\n",input);
    return;
    }
    if(input[now]>='0'&&input[now]<='9'){
    /* Number, continue to the next character */
    dfs(input,now+1,len);
    }else{
    /* Convert to lowercase */
    if(upper(input[now])==1)
    input[now]=input[now]-'A'+'a';
    dfs(input,now+1,len);
    /* Convert to uppercase */
    if(upper(input[now])==2)
    input[now]=input[now]-'a'+'A';
    dfs(input,now+1,len);
    }
    }
    int main(){
    char input[105];
    while(scanf("%s",input)!=EOF){
    dfs(input,0,strlen(input));
    }
    return 0;
    }
  • 第二種作法是維護一個數字陣列放 0 或 1
    當數字是 0 時代表小寫
    當數字是 1 時代表大寫
    這個數字陣列從 0 開始印答案
    每次加 1 ,然後印出答案
    (簡單來說就是二進位加法的意思)
    所以假設有兩個字母 ab
    順序就是 00 → 01 → 10 → 11
         ab → aB → Ab → AB

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    /*****************************************
    Filename:cp2_final_p4_2.c
    Author:Willy Chen(willychen.org)
    Date:2018.08.14
    *****************************************/
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int main(){
    char input[105];
    while(scanf("%s",input)!=EOF){
    int len = strlen(input);
    int lett[105]={0}; /* -1:number 0:lowercase 1:uppercase */
    int alpha=0; /* The number of alphabets */
    /* Convert to lowercase */
    for(int i=0;i<len;i++){
    if(input[i]>='A'&&input[i]<='Z'){
    input[i]=input[i]-'A'+'a';
    }
    if(input[i]>='0'&&input[i]<='9'){
    lett[i]= -1;
    }else{
    alpha++;
    }
    }
    /* Calculate the number of lines of strings */
    int times=1;
    for(int i=0;i<alpha;i++){
    times *= 2;
    }
    /* Print the answer */
    while(times--){
    /* Print strings */
    for(int i=0;i<len;i++){
    if(lett[i]==-1){
    /* Print number */
    printf("%c",input[i]);
    }else if(lett[i]==0){
    /* Print lowercase */
    printf("%c",input[i]);
    }else{
    /* Print uppercase */
    printf("%c",input[i]-'a'+'A');
    }
    }
    printf("\n");
    /* Plus 1 */
    for(int i=len-1;i>=0;i--){
    if(lett[i]!=-1){
    if(lett[i]==0){
    lett[i]=1;
    break;
    }else{
    lett[i]=0;
    continue;
    }
    }
    }
    }
    }
    return 0;
    }

    其實兩種作法的想法算是一樣的

就是要按照順序把答案印出來


評論

 無法加載Disqus評論系統,請確保您的網絡能夠正常訪問。



本站使用 Volantis 作為主題