单词接龙

题目描述

单词接龙的规则是:

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

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

输入描述

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

备注:

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

输出描述

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

示例1

输入:

0
6
word
dd
da
dc
dword
d

输出:

worddwordda

示例2

输入:

4
6
word
dd
da
dc
dword
d

输出:

dwordda

题解

Python

def main():
    # 读取输入
    first_word_index = int(input())
    word_count = int(input())
    assert 0 <= first_word_index < word_count
    words = []
    for i in range(word_count):
        words.append(input())

    s = words[first_word_index]
    # 将第一个单词从字典中去除, 然后重整字典
    words.pop(first_word_index)

    # 开始接龙, 如果字典已经空了, 就终止
    while words:
        next_char = s[-1]
        last_word_index = -1
        last_word = ""

        # 遍历字典, 找到以 next_char 开头的单词
        for i in range(len(words)):
            word = words[i]
            # 将当前词更新为 last_word 的条件有:
            # - 当前词的长度比上个词长
            # - 或者当前词的字典序小于上个词
            if word.startswith(next_char):
                if len(word) > len(last_word) or (len(word) == len(last_word) and word < last_word):
                    last_word = word
                    last_word_index = i
        # 没有找到合适的单词, 终止循环
        if last_word_index == -1:
            break
    
        # 接龙, 并将该单词从字典中移除
        s += last_word
        words.pop(last_word_index)

    print(s)

if __name__ == "__main__":
    main()

Rust

use std::io::{stdin, BufRead};

fn main() {
    // 读取输入
    let mut line = String::new();
    let ret = stdin().lock().read_line(&mut line);
    assert!(ret.is_ok());
    let first_word_index: usize = line.trim().parse().unwrap();

    line.clear();
    let ret = stdin().lock().read_line(&mut line);
    assert!(ret.is_ok());
    let word_count: usize = line.trim().parse().unwrap();
    assert!(first_word_index < word_count);

    let mut words: Vec<String> = Vec::with_capacity(word_count);
    for _i in 0..word_count {
        line.clear();
        let ret = stdin().lock().read_line(&mut line);
        assert!(ret.is_ok());
        words.push(line.trim().to_owned());
    }

    // 将第一个单词从字典中去除, 然后重整字典
    let mut ans: String = words.remove(first_word_index).to_owned();

    // 开始接龙, 如果字典已经空了, 就终止
    while !words.is_empty() {
        let next_char: char = ans.chars().last().unwrap();
        let mut last_word_index = usize::MAX;
        let mut last_word = String::new();

        // 遍历字典, 找到以 next_char 开头的单词
        for (index, word) in words.iter().enumerate() {
            // 将当前词更新为 last_word 的条件有:
            // - 当前词的长度比上个词长
            // - 或者当前词的字典序小于上个词
            if word.starts_with(next_char)
                && (word.len() > last_word.len()
                    || (word.len() == last_word.len() && *word < last_word))
            {
                last_word = word.to_string();
                last_word_index = index;
            }
        }
        // 没有找到合适的单词, 终止循环
        if last_word_index == usize::MAX {
            break;
        }

        // 接龙, 并将该单词从字典中移除
        ans.push_str(&last_word);
        words.remove(last_word_index);
    }

    // 打印结果
    println!("{ans}");
}