面试题17.13.恢复空格

链接：面试题17.13.恢复空格
难度：Medium
标签：字典树、数组、哈希表、字符串、动态规划、哈希函数、滚动哈希
简介：设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

题解 1 - typescript

• 编辑时间：2020-07-09
• 执行用时：360ms
• 内存消耗：73.3MB
• 编程语言：typescript
• 解法介绍：构造前缀树，dp[i]为前 i 项有 n 项多余，每次遍历时向前比对是否匹配。

class Trie {
  private _tree = new Map<string, Trie>();
  constructor(public end = false) {}
  get(char: string): Trie | undefined {
    return this._tree.get(char);
  }
  add(word: string): void {
    if (word.length === 1) {
      const t = this._tree.get(word);
      if (t) {
        t.end = true;
      } else {
        this._tree.set(word, new Trie(true));
      }
      return;
    }
    const chars = word;
    const firstChar = chars[0];
    const surplusChar = chars.substr(1);
    const char = this._tree.get(firstChar);
    if (char) {
      this._tree.get(firstChar)?.add(surplusChar);
    } else {
      const trie = new Trie();
      trie.add(surplusChar);
      this._tree.set(firstChar, trie);
    }
  }
  toString(intend = 0): string {
    const blank = ''.padStart(intend);
    let res = '';
    for (const [k, v] of this._tree) {
      res += `
${intend === 0 ? '===\n' : ''}${blank}${k}${v.end ? ']' : ''}`;
      res += `${blank}${v ? v.toString(intend + 1) : ''}`;
    }
    return res;
  }
  print() {
    console.log(this.toString());
  }
}
function respace(dictionary: string[], sentence: string): number {
  const trie = new Trie();
  dictionary.forEach(word => {
    trie.add(word.split('').reverse().join(''));
  });
  const len = sentence.length;
  const dp = new Array(len + 1).fill(Infinity);
  dp[0] = 0;
  let rootTrie: Trie = trie;
  for (let i = 1; i <= len; i++) {
    dp[i] = dp[i - 1] + 1;
    for (let j = i; j >= 1; j--) {
      const char = sentence[j - 1];
      const nextTrie = rootTrie.get(char);
      if (!nextTrie) {
        break;
      } else if (nextTrie.end) {
        dp[i] = Math.min(dp[i], dp[j - 1]);
      }
      if (dp[i] == 0) {
        break;
      }
      rootTrie = nextTrie;
    }
    rootTrie = trie;
  }
  return dp[len];
}