# 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 relatipnships as a list of lists, and given 2 names, return all known “sequances” of relationships from name1 to name2.

Example:
Input: relationships =[[“Bart”, “brother”, “Lisa”], [“Bart”, “son”, “Homer”], [“Marge”, “wife”, “Homer”],[“Lisa”, “daughter”, “Homer”]], name1 = “Bart”, name2 = “Homer”
Output: [“Bart son Homer”, “Bart brother Lisa daughter Homer”]

``````import java.util.*;

public class relation {

public static List<String> relationship(String[][] relationships, String name1, String name2, Set<String> visited) {
Map<String, Map<String, String>> reMap = new HashMap<>();
List<String> result = new ArrayList<>();
for (String[] re : relationships) {
reMap.computeIfAbsent(re[0], k -> new HashMap<>()).put(re[2], re[1]);
}
if (!reMap.containsKey(name1)) {
return result;
}
else {
visited.add(name1);
Map<String, String> valMap = reMap.get(name1);
for (String k : valMap.keySet()) {
if (visited.contains(k) && k != name2) {
continue;
} else {
visited.add(k);
if (k.equals(name2)) {
result.add(name1 + " " + valMap.get(k) + " " + name2);
} else {
for (String str: relationship(relationships, k, name2, visited)) {
result.add(name1 + " " + valMap.get(k) + " " + str);
}

}
}
}
}
return result;
}

public static void main(String[] args) {
String[][] rel = {
{"Bart", "brother", "Lisa"},
{"Bart", "son", "Homer"},
{"Marge", "wife", "Homer"},
{"Lisa", "daughter", "Homer"},
{"Lisa", "daughter", "Marge"},
{"Marge", "daughter", "Mary"},
{"Mary", "mother-in-law", "Homer"},
{"Mary", "grandaughter", "Lisa"}
};
String name1 = "Bart";
String name2 = "Homer";
Set<String> visited = new HashSet<String>();

for (String s : relationship(rel, name1, name2, visited)) {
System.out.println(s);
}

/*output
Bart son Homer
Bart brother Lisa daughter Marge wife Homer
Bart brother Lisa daughter Marge daughter Mary mother-in-law Homer
Bart brother Lisa daughter Homer
*/
}
}
``````

2 Likes
``````                if (k.equals(name2)) {
result.add(name1 + " " + valMap.get(k) + " " + name2);
} else {
for (String str: relationship(relationships, k, name2)) {
result.add(name1 + " " + valMap.get(k) + " " + str);
}
}
``````

1 Like

``````	private List<List<String>> generateList(String start, String end, Map<String, List<String>> map, List<String> sol,
List<List<String>> res) {
if (start.equals(end)) {
sol.add(start);
res.add(new ArrayList<>(sol));
sol.remove(sol.size() - 1);
return res;
}

List<String> words = map.get(start);
if (words == null) {
return res;
}

sol.add(start);
for (String word : words) {
generateList(word, end, map, sol, res);
}
sol.remove(sol.size() - 1);
return res;
}

``````

1 Like

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