[HDOJ2572]终曲

Problem Description

最后的挑战终于到了！
站在yifenfei和MM面前的只剩下邪恶的大魔王lemon一人了！战胜他，yifenfei就能顺利救出MM。
Yifenfei和魔王lemon的挑战很简单：由lemon给出三个字符串，然后要yifenfei说出第一串的某个子串，要求该子串长度最小，并且同时包含第2个串和第3个串。
特别地，如果有多个这样的子串，则请输出字母序最小的一个。

Input

输入数据首先是一个整数C，表示测试数据有C组；
接着是C组数据，每组包含三行字符串，第一个字符串长度大于1小于100
后面两个串的长度大于1且小于10

Output

请对应每组输入数据输出满足条件的最短子串；
如果没有，请输出 No

Sample Input

2

abcd

ab

bc

abc

ab

bd

Sample Output

abc

No

好久没做题了,找了个字符串稍微难一点的水题来做XD

(PS:主要我是仙剑骨灰迷~~~~~~超喜欢剑仙云天青和他的儿子咯)

这个题目关键就是在于找到相同长度的子串的时候，要按照字典序升序来输出，因此这里需要比较一下。

大JAVA的TreeSet就派上用场啦。

步骤:

1.找到子串b,c是否被包含于a中,否则"No"

2.如果找打了,找出他们出现的位置(dist)的距离的绝对值最小值.

3.放入TreeSet,剔除长于本次找到的子串.

4.输出字典序升序答案.

JAVA CODE:

import java.util.Scanner;
import java.util.TreeSet;

public class Main {

    public static String go( String a, String b, String c ) {
        TreeSet<String> set = new TreeSet<String>();
        if( !a.contains( b ) || !a.contains( c ) ) {
            return "No";
        } else {
            int dist = Integer.MAX_VALUE;
            for( int i = 0; i < a.length(); i++ ) {
                int index1 = a.indexOf( b, i );
                int index2 = a.indexOf( c, i );
                if( index1 >= 0 && index2 >= 0 ) {
                    if( Math.abs( index1 - index2 ) <= dist ) {
                        int start = 0;
                        int end = 0;
                        if( index2 > index1 ) {
                            end = index2 + c.length();
                            start = index1;
                        } else {
                            end = index1 + b.length();
                            start = index2;
                        }
                        dist = Math.abs( index1 - index2 );
                        String result = a.substring( start, end );
                        if(set.size() > 0){
                            String pre = set.first();
                            if(result.length() < pre.length()){
                                set.pollFirst();
                            }
                        }
                        set.add( result );
                    }
                }
            }
        }
        return set.first();
    }

    public static void main( String[] args ) {
        Scanner sc = new Scanner( System.in );
        if( sc.hasNext() ) {
            int num = sc.nextInt();
            for( int i = 0; i < num; i++ ) {
                String a = sc.next();
                String b = sc.next();
                String c = sc.next();
                System.out.println( go( a, b, c ) );
            }
        }
    }
}