【洛谷】P1019 单词接龙（C++/Java）

传送门：洛谷P1019

思路：本题题目为单词接龙，所以顾名思义，第二个接入的单词前缀要与前一个单词的后缀相同才能连到一起。做本题之前，大家可以先去了解一下KMP算法，这样触类旁通，可以解出更多的题。

KMP算法详解

理清本题要点（限制条件）：

1. 接龙的单词要的前缀要与前一个单词的后缀相同
2. 每个单词的引用不超过两次
3. 输入的最后一行是“龙”的开头

C++代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>using namespace std;string str[25], ret; // str[] 存储你输入的n个字符串，ret 是“龙”
int n, num[25], sum = 0; // num[] 为每个字符串使用过的次数，sum记录“龙”的最大长度
char st; // st 为首字母// 计算重叠部分长度的函数
int overlap(int d) 
{int rlen = ret.size();int dlen = str[d].size();// 外层循环计算加入下一个单词后，“龙”增加的长度ifor (int i = 1; i < min(rlen,dlen); i++){bool flag = true;// 内层循环作比较，遇到不想同的字符跳出本层循环，如果全部相同就返回for (int j = 0; j < i; j++){if (ret[rlen - i + j] != str[d][j]){flag = false;break;} }if (flag)return i;}// 如果都不相同，返回0return 0;
}// 搜索算法
void dfs()
{int len = ret.size();sum = max(sum, len);for (int i = 0; i < n; i++){if (num[i] >= 2)continue;int x = overlap(i);if (x > 0) // 若是有重叠部分，则可以接龙{ret += str[i].substr(x);num[i]++;dfs();ret.erase(len); // 回溯时要将添加的部分删去num[i]--;}}return;
}int main()
{cin >> n;for (int i = 0; i < n; i++)cin >> str[i];cin >> st;for (int i = 0; i < n; i++){if (str[i][0] == st){ret = str[i];num[i]++;dfs();memset(num, 0, sizeof(num));}}cout << sum << endl;return 0;
}

Java代码：

import java.util.Arrays;
import java.util.Scanner;public class Main {static String[] str = new String[25];static String ret;static int n, sum = 0;static int[] num = new int[25];static char st;public static int overlap(int d) {int rlen = ret.length();int dlen = str[d].length();char[] rets = ret.toCharArray();char[] strs = str[d].toCharArray();for (int i = 1; i < Math.min(rlen, dlen); i++) {boolean flag = true;for (int j = 0; j < i; j++) {if (rets[rlen - i + j] != strs[j]) {flag = false;break;}}if (flag)return i;}return 0;}public static void dfs() {int len = ret.length();sum = Math.max(sum, len);for (int i = 0; i < n; i++) {if (num[i] >= 2)continue;int x = overlap(i);String temp = ret;if (x > 0) {ret = ret + str[i].substring(x);num[i]++;dfs();ret = temp;num[i]--;}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();for (int i = 0; i < n; i++)str[i] = sc.next();st = sc.next().charAt(0);for (int i = 0; i < n; i++) {if (str[i].charAt(0) == st) {ret = str[i];num[i]++;dfs();Arrays.fill(num, 0);}}System.out.println(sum);}
}

我亲测的两种语言时间与空间上的差距，同一种算法下，C++遥遥领先！
所以大家如果想学算法的话，建议学一学C++语言，真的会少很多痛苦哦