字符串压缩问题——程序员解法

  在http://www.cnblogs.com/bestDavid/p/Stringeliminate.html看到了一个有趣的小题:

给定一个字符串,仅由a,b,c 3种小写字母组成。当出现连续两个不同的字母时,你可以用另外一个字母替换它。
如有ab或ba连续出现,你把它们替换为字母c;
有ac或ca连续出现时,你可以把它们替换为字母b;
有bc或cb连续出现时,你可以把它们替换为字母a。
你可以不断反复按照这个规则进行替换,你的目标是使得最终结果所得到的字符串尽可能短,求最终结果的最短长度。
输入:字符串。长度不超过200,仅由abc三种小写字母组成。
输出:按照上述规则不断消除替换,所得到的字符串最短的长度。
例如:
输入cab,输出2。因为我们可以把它变为bb或者变为cc。         
输入bcab,输出1。尽管我们可以把它变为aab -> ac -> b,也可以把它变为bbb,但因为前者长度更短,所以输出1。

  这个题目原博文中是用“数学”的方法给出解答的,但其推理证明过程(包括引文给出的证明过程)并不严谨,结论依据不足。所以这里用程序员的思考方法给出解答。

  程序员的方法无非就是老老实实地进行替换。对每一种可以替换的情形都进行替换。例如对bcab,可以替换为aab,bbb和bcc。题中提到“可以不断反复按照这个规则进行替换”,所以上面的各个情况又可以进一步
  aab:
  aab->ac->b 长度为1.
  bbb:
  无不同字母,无法进一步替换。长度为3
  bcc:
  bcc->ac->b 长度为1
  综上,对bcab进行不断变换,所得到的字符串的最短长度为1。
  因此,很容易给出代码总体结构。 

 1 #include <stdio.h>
 2 
 3 #define MAX 200
 4 
 5 typedef char String[ MAX + 1 ];
 6 
 7 #define N(x) N_(x)
 8 #define N_(x) #x
 9 
10 void input( char * );
11 unsigned min_len( char * );
12 
13 int main( void )
14 {
15    String str;  
16    
17    input( str );
18 
19    printf("替换最终结果的最短长度为%u。
" , min_len( str ) );
20 
21    return 0;
22 }
23 
24 unsigned min_len( char *s )
25 {
26    
27 }
28 
29 void input( char *s )
30 {
31    puts("输入字符串");
32    scanf("%"N(MAX)"[abc]s",s);
33    puts("要确定长度的字符串为:");
34    puts( s );
35 }

   其中宏 MAX 为字符串初始最大长度,为了给字符串结尾的留出空间,存储字符串的字符数组的最大尺寸为 MAX + 1 。由于这种类型在整个代码中频繁用到,所以用 typedef 为其取了一个统一的名字。
  函数input()输入字符串由于字符串由a、b、c三种字母组成,所以禁止输入其他字符这就是 scanf("%"N(MAX)"[abc]s",s); 中[abc]的目的。又考虑到防止数组输入越界,因此为输入增加了宽度限制——N(MAX),宏展开后的结果为"200"。所以"%"N(MAX)"[abc]s"就是"%200[abc]s"。

  下面考虑min_len( char *s )函数。基本思路就是先求出s的初始长度

int len = strlen( s );

  然后从头至尾检查是否有相邻的相异字符,如有则替换:

reduce( newstr , s , i1 );

  这样将得到一个新的字符串newstr。设新字符串的长度为

int newlen ;

  新字符串最终长度显然仍然可以用min_len()求得:

newlen = min_len( newstr );

  如果newlen小于len,则将len记为newlen的值。

         if ( newlen < len )
         {
            len = newlen ;
         }

  这样返回最后的len就是变换后的最短长度。min_len函数完整代码如下:

 1 unsigned min_len( char *s )
 2 {
 3    int len = strlen( s );
 4    int i = 0 ;
 5    while ( s[i] != '' && s[i+1] != '' )
 6    {
 7       if ( s[i] != s[i+1] )
 8       {
 9          String newstr ;
10          unsigned newlen ;
11          
12          reduce( newstr , s , i );
13          newlen = min_len( newstr );
14          if ( newlen < len )
15          {
16             len = newlen ;
17          }
18       }
19       i ++ ;
20    }
21    return len;
22 }

  再来看一下reduce()函数。完成三件事:

  1. 将ss[i]前面的字符——一共i个,copy到st中:strncpy( st , ss , i );
  2. 根据ss[i],ss[i+1]求出替换字符,并写到st[i]中。
  3. 将ss中ss[i+1]以后的部分copy到st中从st[i+1]开始的位置。

  至此,问题解决,全部代码完成。下面是完整的代码。

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define MAX 200
 5 
 6 typedef char String[ MAX + 1 ];
 7 
 8 #define N(x) N_(x)
 9 #define N_(x) #x
10 
11 void input( char * );
12 unsigned min_len( char * );
13 void reduce( char * , char * , unsigned );
14 char turn ( char , char );
15 
16 int main( void )
17 {
18    String str;  
19    
20    input( str );
21 
22    printf("替换最终结果的最短长度为%u。
" , min_len( str ) );
23    
24    return 0;
25 }
26 
27 char turn ( char c1 , char c2 )
28 {
29    return 'a' + 'b' + 'c' - c1 - c2 ;
30 }
31 
32 void reduce( char * st , char * ss , unsigned i )
33 {
34    strncpy( st , ss , i );
35    st[i] = turn ( ss[i] , ss[i+1] );
36    strcpy( st + i + 1 , ss + i + 2 );
37 }
38 
39 unsigned min_len( char *s )
40 {
41    int len = strlen( s );
42    int i = 0 ;
43    while ( s[i] != '' && s[i+1] != '' )
44    {
45       if ( s[i] != s[i+1] )
46       {
47          String newstr ;
48          unsigned newlen ;
49          
50          reduce( newstr , s , i );
51          newlen = min_len( newstr );
52          
53          if ( newlen < len )
54             len = newlen ;
55       }
56       i ++ ;
57    }
58    return len;
59 }
60 
61 void input( char *s )
62 {
63    puts("输入字符串");
64    scanf("%"N(MAX)"[abc]s",s);
65    
66    puts("要确定长度的字符串为:");
67    puts( s );
68 }

补记:
万仓一黍 网友就这个问题给出了一个彻底的数学证明 《算法:字符串消除问题的数学证明》 ,根据其结论可以得到更简洁的算法。

另,晓得飞天千秋雪 网友应邀也给出了一个漂亮的证明——《字符串压缩问题》。

原文地址:https://www.cnblogs.com/pmer/p/3293038.html