【笔试真题记录】2023滴滴编程第二题

题目：
现在有n个由大写英文字符组成的字符串，且这些字符串不会互相包含，也不会相等。现在想知道有哪些字符串满足如下条件。设满足条件的字符串为S，存在其他的两个字符串拼接在一起后，能通过去除一个非空前缀和一个非空后缀变为字符串S。这两个用于拼接的字符串可以是同一个，也可以为S。

输入：
第一行一个正整数n，表示字符串的个数。接下来n行，每行输入一个由大写英文字符组成的字符串。
输出：
第一行一个正整数m表示符合条件的字符串数量。接下来输出m行，每行一个由大写英文字符组成的字符串，表示这个字符串符合条件。按照字典序升序输出。

笔试结束了才写出来，只能保证通过测试案例。

import java.util.*;public class Didi {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();scanner.nextLine();String[] strings = new String[n];for (int i = 0; i < n; i++) {strings[i] = scanner.nextLine();}List<String> result = new ArrayList<>();for (int i = 0; i < n; i++) {String s = strings[i];boolean valid = false;for (int j = 0; j < n; j++) {for (int k = 0; k < n; k++) {String concat = strings[j] + strings[k];if (concat.substring(1,concat.length()-1).contains(s)) {valid = true;break;}}if (valid) break;}if (valid) {result.add(s);}}Collections.sort(result);System.out.println(result.size());for (String s : result) {System.out.println(s);}}
}

测试数据：

输入：
10
KPZOKNSTGLUNPPDKPFFW
NDPKU
KPFFWN
CCHXNNY
GWSGZ
NNYCCHX
FMVKSOHOPGZWG
SGZNNYCC
PKUFMVKSOHOPG
CCSGZN输出：
6
CCHXNNY
CCSGZN
KPFFWN
NNYCCHX
PKUFMVKSOHOPG
SGZNNYCC