讨论一道狗家近期面试题word extention

最近总看到一道狗爹家的面经， 大意是返回string里连续重复三遍及以上的character的起始和结束位置 （就是word exten

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

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

啊）。写了个trie版本，求指正

1. class TrieNode {
   
2.         boolean hasWord;
   
3.         TrieNode [] children;
   
4.         public TrieNode() {
   
5.                 this.hasWord = false;
   
6.                 this.children = new TrieNode[26];
   
7.         }
   
8. }
   
9. 
   
10. public class WordExtension {
    
11.        
    
12.         TrieNode root;
    
13.        
    
14.         public List<int[]> getExtension(String s) {
    
15.                 char[] chs = s.toCharArray();
    
16.                 int right = 0;
    
17.                 List<int[]> ans = new ArrayList<>();
    
18.                 while(right < chs.length) {
    
19.                         int left = right;
    
20.                         while (right  < chs.length && chs[right] == chs[left]) {
    
21.                                 right++;
    
22.                         }
    
23.                         if (right - left >= 3) {
    
24.                                 int[] cur = new int[2];
    
25.                                 cur[0] = left;
    
26.                                 cur[1] = right-1;
    
27.                                 ans.add(cur);
    
28.                         }
    
29.                 }
    
30.                 return ans;
    
31.         }
    
32.        
    
33.         public boolean isExist(String s, String[] dict) {
    
34.                 this.root = new TrieNode();
    
35.                 buildDictionary(dict);
    
36.                 List<int[]> extentions = this.getExtension(s);
    
37.                 return valid(s, 0, root, extentions, 0);
    
38.         }
    
39.        
    
40.         private boolean valid(String s, int index, TrieNode cur, List<int[]> extentions, int loc) {
    
41.                 if (index == s.length()) return cur.hasWord;
    
42.                
    
43.                 char c = s.charAt(index);
    
44.                 if (cur.children[c-'a'] == null) {
    
45.                         return false;
    
46.                 }
    
47.        
    
48.                 if (loc < extentions.size() && index == extentions.get(loc)[0]) {
    
49.                         int next = index;
    
50.                         boolean res = false;
    
51.                         for (; next <= extentions.get(loc)[1]; next++) {
    
52.                                 res |= valid(s, next + 1 , cur.children[c-'a'], extentions, loc + 1);
    
53.                         }
    
54.                         return res;
    
55.                 }
    
56.                 else {
    
57.                         return valid(s, index+1 , cur.children[c-'a'], extentions, loc);
    
58.                 }
    
59.         }
    
60.        
    
61.         private void buildDictionary(String[] dict) {
    
62.                 for (String s : dict) {
    
63.                         insert(s, 0, root);
    
64.                 }
    
65.         }
    
66.        
    
67.         private void insert(String s, int index, TrieNode cur ) {
    
68.                 if (index == s.length()) {
    
69.                         cur.hasWord = true;
    
70.                         return;
    
71.                 }
    
72.                 char c = s.charAt(index);
    
73.                 if (cur.children[c-'a'] == null) {
    
74.                         cur.children[c-'a'] = new TrieNode();
    
75.                 }
    
76.                 insert(s, index+1 , cur.children[c-'a']);
    
77.         }
    
78. }

复制代码

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

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

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

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

不hide了，大家随便看吧，有好的想法求多多指教

我觉得用bfs做也可以

lz说的是利口巴灵酒吗

我电面的题目

我想的没那么复杂
用双指针做的
followup也很简单，但要考虑helllo这种词的情况

吟游诗人刘小翠 发表于 2018-11-5 07:05
lz说的是利口巴灵酒吗

啊感谢感谢，看了一下应该确实是

ilidans 发表于 2018-11-5 07:24
我电面的题目

我想的没那么复杂

请问helllo是什么意思呢？求详情

mtrsen 发表于 2018-11-5 05:19
我觉得用bfs做也可以

对是的，应该是可以的

飞人殿下 发表于 2018-11-5 08:10
请问helllo是什么意思呢？求详情

helllo是在符合要求的 我当时直接把所有重复的都删除了就留了一个 就会出现helllo--> helo-->False这种错误的情况

ilidans 发表于 2018-11-5 09:35
helllo是在符合要求的 我当时直接把所有重复的都删除了就留了一个 就会出现helllo--> helo-->False这种错 ...

明白，所以你是直接把这个要查询的word处理成了最简化的string然后去查是吗