[Leetcode][程序员面试金典][面试题17.13][JAVA][恢复空格][动态规划][Trie][字符串哈希]

布满荆棘的人生 2023-02-24 13:27 12阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 动态规划 ######

动态规划流程  
**第 1 步：设计状态**  
dp\[i\] 表示字符串的前 i 个字符的最少未匹配数。

**第 2 步：状态转移方程**  
假设当前我们已经考虑完了前 i -1个字符了，对于前 i 个字符对应的最少未匹配数：

第 i 个字符未匹配，则 dp\[i\] = dp\[i+1\] + 1，即不匹配数加 1;  
遍历前 i -1个字符，若以其中某一个下标 j 为开头、以第 i 个字符为结尾的字符串正好在词典里，则 dp\[i\] = min(dp\[ i \], dp\[ j \]) 更新 dp\[i\]。

**第 3 步：考虑初始化**  
int\[\] dp = new int\[n+1\];  
dp\[0\] = 0;  
**第 4 步：考虑输出**  
dp\[n\];

**时间复杂度：O(N^3) 空间复杂度：O(N)**

class Solution { 
        public int respace(String[] dictionary, String sentence) { 
            Set<String> dic = new HashSet<>();
            for(String str: dictionary) dic.add(str);
    
            int n = sentence.length();
            //dp[i]表示sentence前i个字符所得结果
            int[] dp = new int[n+1];
            for(int i=1; i<=n; i++){ 
                dp[i] = dp[i-1]+1;  //先假设当前字符作为单词不在字典中
                for(int j=0; j<i; j++){ 
                    if(dic.contains(sentence.substring(j,i))){ 
                        dp[i] = Math.min(dp[i], dp[j]);
                    }
                }
            }
            return dp[n];
        }
    }

###### 2. Trie字典树优化 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
**复杂度分析**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]

class Solution { 
        public int respace(String[] dictionary, String sentence) { 
            int n = sentence.length();
    
            Trie root = new Trie();
            for (String word: dictionary) { 
                root.insert(word);
            }
    
            int[] dp = new int[n + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            for (int i = 1; i <= n; ++i) { 
                dp[i] = dp[i - 1] + 1;
    
                Trie curPos = root;
                for (int j = i; j >= 1; --j) { 
                    int t = sentence.charAt(j - 1) - 'a';
                    if (curPos.next[t] == null) { 
                        break;
                        //单词终结标志
                    } else if (curPos.next[t].isEnd) { 
                        dp[i] = Math.min(dp[i], dp[j - 1]);
                    }
                    if (dp[i] == 0) { 
                        break;
                    }
                 
                    curPos = curPos.next[t];
                }
            }
            return dp[n];
        }
    }
    
    class Trie { 
        public Trie[] next;
        public boolean isEnd;
        
        public Trie() { 
            next = new Trie[26];
            isEnd = false;
        }
    
        public void insert(String s) { 
            Trie curPos = this;
    
            for (int i = s.length() - 1; i >= 0; --i) { 
                int t = s.charAt(i) - 'a';
                if (curPos.next[t] == null) { 
                    curPos.next[t] = new Trie();
                }
                curPos = curPos.next[t];
            }
            //给遍历的时候的单词终结标志
            curPos.isEnd = true;
        }
    }

###### 3. 字符串哈希 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
**复杂度分析**  
![在这里插入图片描述][20200709172101864.png]

class Solution { 
        static final long P = Integer.MAX_VALUE;
        static final long BASE = 41;
    
        public int respace(String[] dictionary, String sentence) { 
            Set<Long> hashValues = new HashSet<Long>();
            for (String word : dictionary) { 
                hashValues.add(getHash(word));
            }
    
            int[] f = new int[sentence.length() + 1];
            Arrays.fill(f, sentence.length());
    
            f[0] = 0;
            for (int i = 1; i <= sentence.length(); ++i) { 
                f[i] = f[i - 1] + 1;
                long hashValue = 0;
                for (int j = i; j >= 1; --j) { 
                    int t = sentence.charAt(j - 1) - 'a' + 1;
                    hashValue = (hashValue * BASE + t) % P;
                    if (hashValues.contains(hashValue)) { 
                        f[i] = Math.min(f[i], f[j - 1]);
                    }
                }
            }
    
            return f[sentence.length()];
        }
    
        public long getHash(String s) { 
            long hashValue = 0;
            for (int i = s.length() - 1; i >= 0; --i) { 
                hashValue = (hashValue * BASE + s.charAt(i) - 'a' + 1) % P;
            }
            return hashValue;
        }
    }

#### 【总结】 ####

###### 1.动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2. Rabin-Karp 字符串编码 (字符串哈希) ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]

###### 3.Trie ######

class Trie { 
        public Trie[] next;
        public boolean isEnd;
        
        public Trie() { 
            next = new Trie[26];
            isEnd = false;
        }
    
        public void insert(String s) { 
            Trie curPos = this;
    
            for (int i = s.length() - 1; i >= 0; --i) { 
                int t = s.charAt(i) - 'a';
                if (curPos.next[t] == null) { 
                    curPos.next[t] = new Trie();
                }
                curPos = curPos.next[t];
            }
            curPos.isEnd = true;
        }
    }

转载链接：https://leetcode-cn.com/problems/re-space-lcci/solution/hui-fu-kong-ge-by-leetcode-solution/  
Rabin-Karp 字符串编码 参考链接：https://leetcode-cn.com/problems/longest-happy-prefix/solution/zui-chang-kuai-le-qian-zhui-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/a1a62405e70f4504b710298b250fe4df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230209/8812cececeb045c5bfd0f1f9bee1f484.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20230209/75f0b716d6e14c8a82ecf1a55d77c76f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20230209/727f3b6840ae475a889fc8c8bf01076d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: /images/20230209/0559dc3481e54ebcb81610da3a25bd9a.png
[20200709172101864.png]: /images/20230209/c919e7b312d64f70af5ee53876a4e441.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]: /images/20230209/573ca3f5651f42a3aec9bc28ef789884.png