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

《程序员》2007第八期之算法擂台 | 二维点集的凸包及其直径(1)

2007-08-01

关键字: 算法字符串行程编码

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

题目:设计一个方法 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();
}
}

StringCode.rar (1.1 KB)
描述: 本帖的代码打包
下载次数: 43