OD华为机试 20

单词接龙

描述

单词接龙的规则是
可用于接龙的单词首字母必须要与前一个单词的尾字母相同
当存在多个首字母相同的单词时，取长度最长的单词
如果长度也相等，则取词典序最小的单词
已经参与接龙的单词不能重复使用

现给定一组全部由小写字母组成的单词数组
并指定其中的一个单词为起始单词，进行单词接龙
请输出最长的单词串
单词串是由单词拼接而成 中间没有空格

示例1：
输入

0
6
word
dd
da
dc
dword
d
1
2
3
4
5
6
7
8

输出

worddwordda
1

说明：
先确定起始单词word
再确定d开头长度最长的单词dword
剩余以d开头且长度最长的由 da dd dc
则取字典序最小的da
所以最后输出worddwordda

示例二：
输入：

4
6
word
dd
da
dc
dword
d
1
2
3
4
5
6
7
8

输出：

dwordda
1

法一

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int index = Integer.parseInt(sc.nextLine());
            int num = Integer.parseInt(sc.nextLine());
            List<String> list = new ArrayList<>();
            for (int i = 0 ; i < num ; i++) {
                list.add(sc.nextLine());
            }

            //加入到字符串中
            StringBuilder sb = new StringBuilder();
            sb.append(list.get(index));
            list.remove(index);

            list.sort(new Comparator<String>() {
                @Override
                public int compare(String w1, String w2) {
                    int len1 = w1.length();
                    int len2 = w2.length();
                    if (len1 == len2) {
                        return w1.compareTo(w2);
                    } else {
                        return len2 - len1;
                    }
                }
            });

            int len = 0;
            do {
                len = sb.length();
                String last = sb.substring(sb.length() - 1);
                for (int i = 0 ; i < list.size() ; i++) {
                    String begin = list.get(i);
                    if (begin.startsWith(last)) {
                        sb.append(begin);
                        list.remove(i);
                        break;
                    }
                }
            } while (sb.length() != len);
            System.out.println(sb.toString());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

算法实现

代码中用到了两种list.remove()，一种是删除索引，另一种是直接删除字符串
链接: List.remove(1)是删除索引还是删除数字1？
链接: Java List.remove()方法：移出列表中的指定元素