查看网站外链代码,wordpress 还原,xp做网站,seopeixun【问题描述】[中等] 【解答思路】
1. 动态规划
动态规划流程 第 1 步#xff1a;设计状态 dp[i] 表示字符串的前 i 个字符的最少未匹配数。
第 2 步#xff1a;状态转移方程 假设当前我们已经考虑完了前 i -1个字符了#xff0c;对于前 i 个字符对应的最少未匹配数#…【问题描述】[中等] 【解答思路】
1. 动态规划
动态规划流程 第 1 步设计状态 dp[i] 表示字符串的前 i 个字符的最少未匹配数。
第 2 步状态转移方程 假设当前我们已经考虑完了前 i -1个字符了对于前 i 个字符对应的最少未匹配数
第 i 个字符未匹配则 dp[i] dp[i1] 1即不匹配数加 1; 遍历前 i -1个字符若以其中某一个下标 j 为开头、以第 i 个字符为结尾的字符串正好在词典里则 dp[i] min(dp[ i ], dp[ j ]) 更新 dp[i]。
第 3 步考虑初始化 int[] dp new int[n1]; dp[0] 0; 第 4 步考虑输出 dp[n];
时间复杂度O(N^3) 空间复杂度O(N)
class Solution {public int respace(String[] dictionary, String sentence) {SetString dic new HashSet();for(String str: dictionary) dic.add(str);int n sentence.length();//dp[i]表示sentence前i个字符所得结果int[] dp new int[n1];for(int i1; in; i){dp[i] dp[i-1]1; //先假设当前字符作为单词不在字典中for(int j0; ji; j){if(dic.contains(sentence.substring(j,i))){dp[i] Math.min(dp[i], dp[j]);}}}return dp[n];}
}
2. Trie字典树优化 复杂度分析
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. 字符串哈希 复杂度分析
class Solution {static final long P Integer.MAX_VALUE;static final long BASE 41;public int respace(String[] dictionary, String sentence) {SetLong hashValues new HashSetLong();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 字符串编码 (字符串哈希) 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/
