机考E卷100分题 - 单词接龙

题目描述

单词接龙的规则是：

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

现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙，

请输出最长的单词串，单词串是单词拼接而成，中间没有空格。

输入描述

输入的第一行为一个非负整数，表示起始单词在数组中的索引K，0 <= K < N ；

输入的第二行为一个非负整数，表示单词的个数N；

接下来的N行，分别表示单词数组中的单词。

备注：

• 单词个数N的取值范围为[1, 20]；
• 单个单词的长度的取值范围为[1, 30]；

输出描述

输出一个字符串，表示最终拼接的单词串。

示例1

输入

0
6
word
dd
da
dc
dword
d
12345678

输出

worddwordda
1

解题思维就是套圈。。。

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int beginIdx = 0; //first number
        int beginArrayLen = 0; //second number,useless number
        int count = 0;
        StringBuilder sb = new StringBuilder();

        while (sc.hasNextLine()) {
            if (count == 0) {
                beginIdx = Integer.parseInt(sc.nextLine());
                continue;
            }
            if (count == 1) {
                beginArrayLen = Integer.parseInt(sc.nextLine());
                continue;
            }
            sb.append(sc.nextLine() + ",");
            count++;
        }
        sb.deleteCharAt(sb.length() - 1);
        String[] beginArray = sb.toString().split(",");//{"word", "dd", "da", "dc", "dword", "d"}

        int getIdx = beginIdx;  //这一轮要取走的序号
        List<String> resultList = new ArrayList<>(); //要接龙的结果集

        while (true) {
            //将选中单词写入结果集，以及将选中单词缓存，方便后续接龙比较
            String word = beginArray[getIdx];
            resultList.add(word);

            //将选中单词取出，形成新的单词数组。
            String[] next = new String[beginArray.length - 1];
            System.arraycopy(beginArray, 0, next, 0, getIdx);
            System.arraycopy(beginArray, getIdx + 1, next, getIdx, beginArray.length - getIdx - 1);


            String tmpWord = null;

            for (int i = 0; i < next.length; i++) {
                if (next[i].substring(0, 1).equals(word.substring(word.length() - 1))) {
                    //若能接上单词，则接上的单词按下面三个规则择优
                    if (tmpWord == null || (tmpWord != null && next[i].length() > tmpWord.length()) || (tmpWord != null && next[i].length() == tmpWord.length() && next[i].compareTo(tmpWord) < 0)) {
                        tmpWord = next[i];
                        getIdx = i;
                    }
                }
            }
            if (tmpWord != null) {
                beginArray = next; //能找到新单词接上
            } else {
                break; //找不到匹配词
            }
        }

        for (String str : resultList) {
            System.out.print(str);
        }


    }