Google seti 电面

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. class Solution {
   
2.   
   
3.   static class Interval {
   
4.     int start;
   
5.     int end;
   
6.   }
   
7.    
   
8.   public static String handler(String s, String[] dict) {
   
9.    
   
10.     PriorityQueue<Interval> pq = new PriorityQueue<Interval>(new Comparator<Interval>() {  
    
11.       public int compare(Interval a, Interval b) {
    
12.         return a.start - b.start;
    
13.       }
    
14.     });
    
15.    
    
16.     for (String word : dict) {
    
17.       int startIndex = 0;
    
18.       int index = 0;
    
19.       index = s.indexOf(word, startIndex);
    
20.       while (index != -1) {
    
21.         Interval interval = new Interval();
    
22.         interval.start = index;
    
23.         interval.end = index + word.length() - 1;
    
24.         pq.offer(interval);
    
25.         startIndex = index + word.length();
    
26.         index = s.indexOf(word, startIndex);
    
27.       }
    
28.     }
    
29.    
    
30.     if (pq.isEmpty()) {
    
31.       return s;
    
32.     }
    
33.    
    
34.     Interval interval = pq.poll();
    
35.     StringBuilder sb = new StringBuilder();
    
36.     int start = 0;
    
37.     while (!pq.isEmpty()) {
    
38.       Interval temp = pq.poll();
    
39.       if (temp.start <= interval.end+1) {
    
40.         interval.end = Math.max(interval.end, temp.end);
    
41.       }
    
42.       else {
    
43.         sb.append(s.substring(start, interval.start));
    
44.         sb.append("<b>");
    
45.         sb.append(s.substring(interval.start, interval.end+1));
    
46.         sb.append("</b>");
    
47.         sb.append(s.substring(interval.end+1, temp.start));
    
48.         start = interval.end + 1;
    
49.         interval = temp;
    
50.       }
    
51.     }
    
52.     sb.append("<b>");
    
53.     sb.append(s.substring(interval.start, interval.end+1));
    
54.     sb.append("</b>");   
    
55.     sb.append(s.substring(interval.end+1, s.length()));
    
56.    
    
57.     return sb.toString();   
    
58.   }
    
59.   
    
60.   public static void main(String[] args) {
    
61.     String s1 = "aaabbcc";
    
62.     String[] dict1 = {"aaa", "aab", "bc"};
    
63.     System.out.println(handler(s1, dict1));
    
64.     String s2 = "abcxyz123";
    
65.     String[] dict2 = {"abc", "123"};
    
66.     System.out.println(handler(s2, dict2));   
    
67.   }

复制代码

写的很挫，没仔细改，但是workable

siren01 发表于 2017-8-8 10:02
写的很挫，没仔细改，但是workable

http://www.geeksforgeeks.org/aho ... -pattern-searching/

AC 自动机

这个好像是LeetCode上面一道题，但是忘记是那一道题了？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

https://leetcode.com/problems/add-bold-tag-in-string/description/

应该就是这道题

可以对input string建立一个trie （实际上是suffix tree）树，每个结点记录经过这个点的suffix，
这样每个单词在tire树查找的时间是单词的长度，和这个单词在input string出现的次数没有关系。

所以总的复杂的是O(n*l + m * m)
n是单词的个数，l是单词的平均长度，m是input string的长度

能麻烦楼主在评论区里再发一下面经吗