Web Address - Uber Prepare

http://www.cnblogs.com/EdwardLiu/p/6364661.html

题目是给你一堆域名，其中一些是另一些的parent，比如.com是.youku.com的parent，然后.youku.com是.service.youku.com的parent这样，然后再给你一个网址，让你在那堆域名中找到这个网址的parent里面最长的一个，然后再往前退一个返回。语言有点不好描述，举个栗子：

Domains:[
“.com”,
“.cn”
“.service.com”
“.net”
“.youku.net”
]
.
url: “yeah.hello.youku.net”

这里.net和.youku.net都是这个url的parent,其中最长的是.youku.net，再往前退一个是hello,所以返回“hello.youku.net”

虽然我觉得这道题用set倒着来就可以解决，但是看到一个Trie的做法也很不错

这里TrieNode.val不再是char, 而是String.  children array也变成了Map<String, TrieNode>

 2     private class TrieNode {
 3         String str;
 4         Map<String, TrieNode> map;
 5         boolean isLeaf;
 6         public TrieNode(String str) {
 7             this.str = str;
 8             this.map = new HashMap<>();
 9             this.isLeaf = false;
10         }
11     }
12     TrieNode root = new TrieNode("#");
13     public static void main(String[] args) {
14         LongestSubDomain lsd = new LongestSubDomain();
15         String[] domains = {".com", ".cn", ".service.com", ".net", ".youku.net"};
16         String url = "yeah.hello.youku.net";
17         for (String str : domains) {
18             lsd.insert(str);
19         }
20         String res = lsd.startWith(url);
21         System.out.println(res);
22     }
23     public void insert(String domain) {
24         String[] temp = domain.split("\\.");
25         TrieNode node = root;
26         for (int i = temp.length - 1; i >= 0; i--) {
27             if (temp[i].length() == 0) continue;
28             if (node.map.containsKey(temp[i])) {
29                 node = node.map.get(temp[i]);
30             } else {
31                 TrieNode newNode = new TrieNode(temp[i]); 
32                 node.map.put(temp[i], newNode);
33                 node = newNode;
34             }
35         }
36         node.isLeaf = true;
37     }
38     public String startWith(String url) {
39         String[] temp = url.split("\\.");
40         TrieNode node = root;
41         String res = "";
42         int index = temp.length - 1;
43         for (int i = temp.length - 1; i >= 0; i--) {
44             if (temp[i].length() == 0) continue;
45             if (node.map.containsKey(temp[i])) {
46                 res = "." + temp[i] + res;
47                 node = node.map.get(temp[i]);
48             } else {
49                 if (!node.isLeaf) {
50                     res = "";
51                 } else {
52                     index = i;
53                 }
54                 break;
55             }
56         }
57         return temp[index] + res;
58     }

我的做法：

 6     public class TrieNode {
 7         String val;
 8         Map<String, TrieNode> children;
 9         boolean end;
10         public TrieNode(String str) {
11             val = str;
12             children = new HashMap<String, TrieNode>();
13             end = false;
14         }
15     }
16     
17 
18         TrieNode root = new TrieNode("");
19         
20         public void insert(String str) {
21             String[] arr = str.split("\\.");
22             TrieNode node = root;
23             for (int i=arr.length-1; i>=0; i--) {
24                 if (arr[i].length() == 0) continue;
25                 if (!node.children.containsKey(arr[i])) {
26                     node.children.put(arr[i], new TrieNode(arr[i]));
27                 }
28                 node = node.children.get(arr[i]);
29             }
30             node.end = true;
31         }
32         
33         public String findLongest(String str) {
34             String[] input = str.split("\\.");
35             TrieNode node = root;
36             StringBuffer res = new StringBuffer(); 
37             for (int i=input.length-1; i>=0; i--) {
38                 String cur = input[i];
39                 if (node.children.containsKey(cur)) {
40                     res.insert(0, cur);
41                     res.insert(0, ".");
42                     node = node.children.get(cur);
43                 }
44                 else {
45                     res.insert(0, cur);
46                     return res.toString();
47                 }
48             }
49             return "";
50         }