# Wish 二面

``````/*
# Suppose we have a series of people relationships that looks something like this:
#        [    ['Bart',  'brother',   'Lisa'    ],
#            ['Bart',  'son',      'Homer'    ],
#            ['Marge', 'wife',     'Homer'    ],
#            ['Lisa',  'daughter', 'Homer'   ]    ]
#
#        i.e. inner lists have len == 3 and are in form name1, relationship, name2
#
# Given a series of relationships as a list of lists, and given two names, return
# all known "sequences" of relationships from name1 to name2
#
# e.g. with the lists above as input, with input names 'Bart' and 'Homer', you should return:
#    ['Bart son Homer', 'Bart brother Lisa daughter Homer']
#

*/
``````

``````public class Solution {
public static void main(String args[] ) throws Exception {
List<List<String>> rel = new ArrayList<>();
getRel(rel, "Bart", "Homer").forEach(x -> System.out.println(x));
}

private static List<String> getRel(List<List<String>> relations, String first, String second) {
List<String> res = new ArrayList<>();
if (relations == null || relations.size() == 0 || first == null ||first.length() == 0|| second == null || second.length() == 0) return res;
if (first.equals(second)) return Arrays.asList(first+" self "+second);
Map<String, List<String[]>> graph = new HashMap<>();
for (List<String> rel: relations) {
if (rel.get(0).equals(rel.get(2))) continue;
graph.computeIfAbsent(rel.get(0), x -> new ArrayList<>()).add(new String[] {rel.get(2), rel.get(1)});
}
if (!graph.containsKey(first)) return res;
dfs(first, second, graph, res, new StringBuilder(), new HashSet<>(), new HashMap<>());
return res;
}

private static void dfs(String first, String second, Map<String, List<String[]>> graph, List<String> res, StringBuilder sb, Set<String> visited, Map<String, List<String>> cached) {
if (!visited.add(first)) return; //if this person has been visited, means there is a loop
if (cached.containsKey(first)) {
int n = sb.length();
for(String no: cached.get(first)) {
sb.setLength(n);
}
return;
}
if (first.equals(second)) {
visited.remove(first);
String[] arr = sb.toString().split(" ");
for (int i = 0; i < arr.length;i+=2) {
int ind = sb.indexOf(arr[i]);
}
return;
}
List<String[]> next = graph.get(first);
if (next == null) return;
sb.append(first);
int len = sb.length();
for (String[] n: next) {
sb.append(" "+n[1]+" ");
dfs(n[0], second, graph, res, sb, visited, cached);
sb.setLength(len);
}
visited.remove(first);
}
}
``````

DFS 先找到一个可行路径
A -> B -> C -> D -> G

remove一下就行了啊

remove什么

visited.remove(first);

e.g. with the lists above as input, with input names ‘Bart’ and ‘Homer’, you should return:

# [‘Bart son Homer’, ‘Bart brother Lisa daughter Homer’]

DFS 先找到一个可行路径
A -> B -> C -> D -> G

A->B->C->D->G

A -> B -> C ->D -> G VISITED: A B C D G
A -> B -> C ->D VISITED: A B C D
A -> B -> C VISITED: A B C
A -> B VISITED: A B
A VISITED: A
A -> E Visited: A E
A -> E -> F visited: A E F
A -> E -> F -> H visited: A E F H
A -> E -> F -> H -> D visited: A E F H D
A -> E -> F -> H -> D -> G visited: A E F H D G

A -> B -> C ->D -> J -> G
A -> B -> C ->D -> K -> G
A -> E -> F -> H -> D -> J -> G
A -> E -> F -> H -> D -> K -> G
D 到 G 可以通过 J 和 K

45分钟3题