首页 > 代码库 > 微软校招编程题"Beautiful String"的状态机解法

微软校招编程题"Beautiful String"的状态机解法

昨天碰巧看到一道微软校招的编程题,题目大意如下:

如果一个字符串包括三组或者更多组的连续升序字母,每组长度相等,那么我们就称这个字符串是Beautiful String如下是一些Beautiful String的例子:abc、cde、aabbcc、aaabbbccc这些不是Beautiful String:abd、cba、aabbc、zab输入一个只含有小写字母的字符串,如果它含有一个Beautiful的子串,就输出YES,否则输出NO输入:第一行是案例个数,之后的每一行是一个数字,一个字符串,数字表示字符串长度,长度小于10MB输出:YES或者NO

很容易想到可以用一个指针依次往前扫描,看是否符合Beautiful的条件,当出现不匹配时,从上次扫描起点的下一个位置开始新的尝试。这种判断过程可以用一个状态机来描述,我之前一直有一种模糊的想法,利用goto来实现不同状态的跳转,现在有这个题作为背景,正好可以试验一下这种想法,代码如下:

#include <stdio.h>#include <stdlib.h>int main(void){    int n, length;    char * str;    char *p;    char * p_bak;    int count[3];    char pre;    scanf("%d", &n);    while (n--)    {        scanf("%d", &length);        str = (char*)malloc(sizeof(char) * (length + 1));        scanf("%s", str);        p = str;        count[0] = 0;        count[1] = 0;        count[2] = 0;        p_bak = p;        goto SECTION_0;    REWIND:        count[0] = 0;        count[1] = 0;        count[2] = 0;        p = ++p_bak;        goto SECTION_0;    SUCCESS:        printf("YES\n");        free(str);        continue;    FAIL:        printf("NO\n");        free(str);        continue;    SECTION_0:        pre = *p;    SECTION_A:        if (*p == \0)            goto FAIL;        if (*p == pre)        {            ++p;            ++count[0];            goto SECTION_A;        }        else if (*p == pre + 1)        {            goto SECTION_B;        }        else        {            goto REWIND;        }    SECTION_B:        if (*p == \0)        {            goto FAIL;            goto FAIL; //向苹果致敬(●‘?‘●),参见 http://coolshell.cn/articles/11112.html        }        if (*p == pre + 1)        {            ++p;            ++count[1];            goto SECTION_B;        }        else if (*p == pre + 2)        {            goto SECTION_C;        }        else        {            goto REWIND;        }    SECTION_C:        if (count[0] != count[1])            goto REWIND;        if (*p == \0)            goto FINAL_CHECK;        if (count[2] == count[1])            goto SUCCESS;        if (*p == pre + 2)        {            ++p;            ++count[2];            goto SECTION_C;        }    FINAL_CHECK:        if (count[2] != count[1])            goto REWIND;        else            goto SUCCESS;    }    return 0;}

 

从没写过这种就像汇编一样的面条代码,写完之后感觉整个人都要坏掉了,当然,一次AC。

(用C实现状态机应该可以利用switch case等功能来实现状态跳转,而不用goto,以后有时间再重构吧。)

微软校招编程题"Beautiful String"的状态机解法