一个关于字符串操作的算法题

最近在网上看到一道关于字符串操作的算法题,不过原题的表述以及给出的数据都有问题.这里我给出修正后的题目:

题目: 设计一个方法 String encode(String str),对字符串str进行如下转换操作为一个新字符串:

         逐个扫描str的每个字符,

         1.若当前字符为'_',则添加"\UL"到新字符串; 否则:

         2.若当前字符表示一大于0的数字N,且该字符不是最后一个字符,则将后继字符添加N+1次到新字符串;否则:

         3.直接添加当前字符到新字符串.

         并且用一个字符'_'将相邻的变换隔开

         并设计一个String decode(String code)方法执行encode的逆操作,即将由encode(str)方法返回的字符串还原为str.

       encode方法的设计没有任何难度,只需要把题目"直译"成程序代码就OK了,有难度的地方在于decode方法.注意到字符串中的字符在encode之后的新字符串中是由'_'分开的,并且原字符串中的每个字符只由这个字符串变换后的字符串以及其后继字符有关,因此我们很容易可以想到先将编码后的字符串按'_'分解成一系列字符串,其中每个字符串对应原字符串的一个字符,然后从后向前一个个求出其所表示的字符.算法的大体想法就是这样,只有一点要注意:类似"4_"这种数字后跟'_'的情形会被编码成一列连续的"_____",应该区分出这种情形并加以处理 .

       其实如果对压缩算法有所了解的话,很容易看出这个题目其实是行程编码( Run-Length Encoding )的一个变形.

下面给出本题的代码:

java 代码

/**
*author: Eastsun
*version: 1.0 2007/8/1
*/
import
 java.util.Scanner;
public
 
class
 StringCode{
    
public
 
static
 
void
 main(String[] args){
        Scanner s =
new
 Scanner(System.in);
        
while
(
true
){
            String text =s.next();
            
if
(
"exit"
.equalsIgnoreCase(text)) 
break
;
            String code =encode(text);
            
boolean
 flags =
true
;       
//用于检测decode是否正确工作的标记
            
try
{
                
if
(!decode(code).equals(text)) flags =
false
;
            }
catch
(IllegalStateException e){
                flags =
false
;
            }
            
if
(flags){
                System.out.println(
"Code :"
 +code);
            }
            
else
{
                System.out.println(
"Error code :"
 +code);
            }
        }
    }
    
private
 
static
 
final
 String ESC_S = 
"\\UL"
;
    
private
 
static
 
final
 
char
   ESC_C = '_';

    
/**
    *将编码后的字符串还原为原字符串
    *@throws IllegalStateException 如果参数str不是一个有效的编码字符串
    */
    
public
 
static
 String decode(String str)
throws
 IllegalStateException{
        StringBuilder sb =
new
 StringBuilder();
        
char
 next =
0xffff
;
        
int
 end =str.length(), start;
        
while
(end>
0
){
            
if
(next==ESC_C&&str.charAt(end-
1
)==ESC_C){
                
for
(start =end -
1
;start>
0
&&str.charAt(start-
1
)==ESC_C;start--);
                
if
(start!=
0
) start ++;
            }
            
else
{
                start =str.lastIndexOf(ESC_C,end -
1
) +
1
;
            }

            String code =str.substring(start,end);

            
if
(code.equals(ESC_S)){
                next = ESC_C;
            }
            
else
 
if
(end-start==
1
){
                next = code.charAt(
0
);
            }
            
else
{
                
for
(
int
 index =
0
;index
                    
if
(code.charAt(index)!= next) 
throw
 
new
 IllegalStateException(
"Illegal code: ["
+start+
","
+end+
"]"
);
                next =(
char
)('
0
'+end-start-
1
);
            }
            sb.insert(
0
,next);
            end =start -
1
;
        }
        
return
 sb.toString();
    }

    
/**
    * 将str编码为新的字符串
    */
    
public
 
static
 String encode(String str){
        StringBuilder sb =
new
 StringBuilder();
        
for
(
int
 index =
0
;index
            
char
 c =str.charAt(index);

            
if
(c==ESC_C){
                sb.append(ESC_S);
            }
            
else
 
if
(c>'
0
'&&c<='
9
'&&index+
1
                
char
 next =str.charAt(index+
1
);
                
for
(
int
 count =c-'
0
';count>=
0
;count--)
                    sb.append(next);
            }
            
else
{
                sb.append(c);
            }

            
if
(index+
1
        }
        
return
 sb.toString();
    }
}

评论

2 楼 Eastsun 2007-08-03  

这个是数字后面跟'_'的情形.
next ==ESC_C说明后继字符为'_',str.charAt(end-1)==ESC_C说明该字符为数字

1 楼 leo_dream 2007-08-03  

if(next==ESC_C&&str.charAt(end-1)==ESC_C){   
                for(start =end -1;start>0&&str.charAt(start-1)==ESC_C;start--);   
                if(start!=0) start ++;   
            }   
这段代码是什么意思