题意
给出一系列字符串,找出一列最长的字符串队列满足:
- A比B少一个字母c
- 除了字母c外,A中所有字母都包含于字母B中。
思路
前面思路想直接暴力模拟,后来发现行不通,需要用到DFS,想到DFS后就是构树,这些就比较简单了。还有C++中还有Hash和二分法之类的。
注意
DFS递归时要搞清Java的值传递和引用传递!!!
代码
import java.io.PrintWriter;
import java.util.*;
/**
* @Author Yuri
* @Date 2020/11/26 10:22
* @Version 1.0
* @Description: POJ2004
*/
class Letters implements Comparable<Letters> {
String sortName, name;
ArrayList<Integer> children = new ArrayList<Integer>();
boolean flag;
Letters(String sortName, String name) {
this.sortName = sortName;
this.name = name;
flag = true;
}
@Override
public int compareTo(Letters o) {
return name.length() - o.name.length();
}
@Override
public String toString() {
return "Letters{" +
"sortName='" + sortName + '\'' +
", name='" + name + '\'' +
", children=" + children +
", flag=" + flag +
'}';
}
}
public class Main {
static PrintWriter out = new PrintWriter(System.out);
static Scanner scanner = new Scanner(System.in);
static Integer n = 0;
static ArrayList<Letters> letters = new ArrayList<Letters>();
static ArrayList<Integer> ans = new ArrayList<Integer>();
public static void stringSort(String s) {
char[] c = s.toCharArray();
Arrays.sort(c);
String ss = new String(c);
letters.add(new Letters(ss, s));
}
public static boolean isOK(String x, String y) {
int i = 0;
while (i < x.length() && x.charAt(i) == y.charAt(i)) i++;
while (++i < y.length()) {
if (y.charAt(i) != x.charAt(i - 1))
return false;
}
return true;
}
public static void dfs(Integer r, ArrayList<Integer> fakeAns) {
Letters lt = letters.get(r);
ArrayList<Integer> fa = new ArrayList<Integer>(fakeAns);
fa.add(r);
if (lt.children.isEmpty()){
if (ans.size() < fa.size()) {
ans = fa;
}
return;
}
for (int i = 0; i < lt.children.size(); i++) {
dfs(lt.children.get(i), fa);
}
}
public static void main(String[] args) {
while (scanner.hasNext()) {
n++;
String s = scanner.next();
stringSort(s);
}
Collections.sort(letters);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
String si = letters.get(i).sortName;
String sj = letters.get(j).sortName;
if (si.length() + 1 == sj.length() && isOK(si, sj)) {
letters.get(i).children.add(j);
letters.get(j).flag = false;
} else if (si.length() + 1 < sj.length()) {
break;
}
}
}
for (int i = 0; i < n; i++) {
ArrayList<Integer> fakeAns = new ArrayList<Integer>();
if (letters.get(i).flag) {
dfs(i, fakeAns);
}
}
for (int i = 0; i < ans.size(); i++) {
System.out.println(letters.get(ans.get(i)).name);
}
}
}