首页 > 专题系列 > Java解POJ > POJ 3096 Surprising Strings [解题报告] Java
2013
11-12

POJ 3096 Surprising Strings [解题报告] Java

Surprising Strings

问题描述 :

The D-pairs of a string of letters are the ordered pairs of letters that are distance D from each other. A string is D-unique if all of its D-pairs are different. A string is surprising if it is D-unique for every possible distance D.

Consider the string ZGBG. Its 0-pairs are ZG, GB, and BG. Since these three pairs are all different, ZGBG is 0-unique. Similarly, the 1-pairs of ZGBG are ZB and GG, and since these two pairs are different, ZGBG is 1-unique. Finally, the only 2-pair of ZGBG is ZG, so ZGBG is 2-unique. Thus ZGBG is surprising. (Note that the fact that ZG is both a 0-pair and a 2-pair of ZGBG is irrelevant, because 0 and 2 are different distances.)

Acknowledgement: This problem is inspired by the "Puzzling Adventures" column in the December 2003 issue of Scientific American.

输入:

The input consists of one or more nonempty strings of at most 79 uppercase letters, each string on a line by itself, followed by a line containing only an asterisk that signals the end of the input.

输出:

For each string of letters, output whether or not it is surprising using the exact output format shown below.

样例输入:

ZGBG
X
EE
AAB
AABA
AABB
BCBABCC
*

样例输出:

ZGBG is surprising.
X is surprising.
EE is surprising.
AAB is surprising.
AABA is surprising.
AABB is NOT surprising.
BCBABCC is NOT surprising.

解题代码:

//* @author popop0p0popo
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
  Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
	boolean flag;
	int index;
	String s;
	String[] pair;
	while (true){
		s=scanner.next();
		if (s.equals("*")){
			break;
		}
		if (s.length()==1){
			System.out.println(s+" is surprising.");
			continue;
		}
		index=0;
		flag=true;
		while (index< s.length()-1){
			pair=new String[s.length()-index-1];
			for (int i=0;i< pair.length ;i++ ){
				pair[i]=""+s.charAt(i)+s.charAt(i+index+1);
			}
			if (!check(pair)){
				flag=false;
				break;
			}
			index++;
		}
		if (flag){
			System.out.println(s+" is surprising.");
		}
		else{
			System.out.println(s+" is NOT surprising.");
		}
	}
  }

  public static boolean check(String[] s){
	for (int i=0;i< s.length-1 ;i++ ){
		for (int j=i+1;j< s.length ;j++ ){
			if (s[i].equals(s[j])){
				return false;
			}
		}
	}
	return true;
 }
}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。