(C卷,100分)- 单词接龙（Java & JS & Python）

题目描述

单词接龙的规则是：

• 可用于接龙的单词首字母必须要前一个单词的尾字母相同；
• 当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词；已经参与接龙的单词不能重复使用。
• 现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙，
• 请输出最长的单词串，单词串是单词拼接而成，中间没有空格。

输入描述

• 输入的第一行为一个非负整数，表示起始单词在数组中的索引K，0 <= K < N ；
• 输入的第二行为一个非负整数，表示单词的个数N；
• 接下来的N行，分别表示单词数组中的单词。

备注：

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

输出描述

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

用例

题目解析

逻辑题，主要考察数组操作，如数组元素删除，数组自定义排序。

我的解题思路如下：

先用splice方法，将起始单词从输入数组中删除，splice会将删除的元素形成一个新数组，我刚好将该数组作为收集接龙单词的链条数组chain。

之后，遍历输入数组中剩下的单词，将它们根据首字母进行分类，同一个首字母的单词存放在一个数组中。存储容器选择对象prefix，首字母作为对象的属性，存放同首单词的数组为对象的属性值。

当统计完后，对每个分类数组进行排序，即优先按照单词长度降序，如果单词长度相同，再按照字典序升序。

之后，取出chain的尾巴元素，再取出尾巴元素单词的尾巴字符tail，如果存在prefix[tail]，则取出prefix[tail]数组的头部元素加入chain中，然后继续循环前面逻辑，如果不存在prefix[tail]，则结束循环，将chain.join('') 当成结果输出。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let k, n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    [k, n] = lines.map(Number);
  }

  if (n && lines.length === n + 2) {
    lines.shift();
    lines.shift();

    console.log(getResult(lines, k));

    lines.length = 0;
  }
});

function getResult(words, k) {
  const chain = words.splice(k, 1);

  const prefix = {};

  for (let word of words) {
    const w = word[0];
    prefix[w] ? prefix[w].push(word) : (prefix[w] = [word]);
  }

  for (let key in prefix) {
    prefix[key].sort((a, b) =>
      a.length != b.length ? b.length - a.length : a > b ? 1 : -1
    );
  }

  while (true) {
    let tail = chain.at(-1).at(-1);

    if (prefix[tail] && prefix[tail].length > 0) {
      chain.push(prefix[tail].shift());
    } else {
      break;
    }
  }

  return chain.join("");
}

Java算法源码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int k = sc.nextInt();
    int n = sc.nextInt();

    String[] words = new String[n];
    for (int i = 0; i < n; i++) words[i] = sc.next();

    System.out.println(getResult(k, n, words));
  }

  public static String getResult(int k, int n, String[] words) {
    ArrayList<String> chain = new ArrayList<>();
    chain.add(words[k]);

    words[k] = null;

    HashMap<Character, LinkedList<String>> prefix = new HashMap<>();
    for (String word : words) {
      if (word != null) {
        char c = word.charAt(0);
        prefix.putIfAbsent(c, new LinkedList<>());
        prefix.get(c).add(word);
      }
    }

    for (Character c : prefix.keySet()) {
      prefix
          .get(c)
          .sort((a, b) -> a.length() != b.length() ? b.length() - a.length() : a.compareTo(b));
    }

    while (true) {
      String tail = chain.get(chain.size() - 1);
      char c = tail.charAt(tail.length() - 1);

      if (prefix.containsKey(c) && prefix.get(c).size() > 0) {
        chain.add(prefix.get(c).removeFirst());
      } else {
        break;
      }
    }

    StringBuilder sb = new StringBuilder();
    for (String s : chain) sb.append(s);
    return sb.toString();
  }
}

Python算法源码

# 输入获取
k = int(input())
n = int(input())
words = [input() for _ in range(n)]


# 算法入口
def getResult():
    chain = [words.pop(k)]

    prefix = {}
    for word in words:
        w = word[0]
        if prefix.get(w) is None:
            prefix[w] = []
        prefix[w].append(word)

    for w in prefix.keys():
        prefix[w].sort(key=lambda x: (-len(x), [ord(i) for i in x]))

    while True:
        tail = chain[-1][-1]

        if prefix.get(tail):
            chain.append(prefix[tail].pop(0))
        else:
            break

    return "".join(chain)


# 调用算法
print(getResult())