记忆化搜索

今天的leetcode每日一题是一道关于记忆化搜索的题目，这里简单记录一下。

这是题目链接：https://leetcode-cn.com/problems/scramble-string/

什么是记忆化搜索

要明白这个，首先要明白什么是搜索。

搜索大家很熟悉，DFS，BFS，深度优先搜索和广度优先搜索。

那记忆化搜索又是什么呢？就是在这个递归搜索过程中，对于一些重复的子问题，找个数据结构记下来上一次计算的结果。

听起来是不是有点像动态规划？

是的，记忆化搜索时递归，自顶向下，而动态规划是把递归的过程抽取成状态转移方程，记忆化数据结构变成DP数组，然后自底向上地去计算。

解题思路

https://leetcode-cn.com/problems/scramble-string/solution/rao-luan-zi-fu-chuan-by-leetcode-solutio-8r9t/

代码实现

我们可以先写出普通的DFS，然后加上某种数据结构去记忆已有的结果防止重复计算

DFS

 const checkIfSimilar = function(i1, i2, length, s1, s2) {
  const freq = new Map();
  for (let i = i1; i < i1 + length; ++i) {
      const c = s1[i];
      freq.set(c, (freq.get(c) || 0) + 1);
  }
  for (let i = i2; i < i2 + length; ++i) {
      const c = s2[i];
      freq.set(c, (freq.get(c) || 0) - 1);
  }
  for (const value of freq.values()) {
      if (value !== 0) {
          return false;
      }
  }
  return true;
}

const dfs = (i1, i2, length, s1, s2) => {
  if (s1.slice(i1, i1 + length) === s2.slice(i2, i2 + length)) {
    return true;
  }

  if (!checkIfSimilar(i1, i2, length, s1, s2)) {
    return false;
  }

  for (let i = 1; i < length; i++) {
    if (dfs(i1, i2, i, s1, s2) && dfs(i1 + i, i2 + i, length - i, s1, s2)) {
      return true
    }
    if (dfs(i1, i2 + length - i, i, s1, s2) && dfs(i1 + i, i2, length - i, s1, s2)) {
      return true;
    }
  }

  return false;
}

var isScramble = function(s1, s2) {
  return dfs(0, 0, s1.length, s1, s2);
};

加上记忆化搜索

var isScramble = function(s1, s2) {
    const length = s1.length;
    memo = new Array(length).fill(0).map(() => new Array(length).fill(0).map(() => new Array(length + 1).fill(0)));
    return dfs(0, 0, length, s1, s2, memo);
};

const dfs = function(i1, i2, length, s1, s2, memo) {
    if (memo[i1][i2][length] !== 0) {
        return memo[i1][i2][length] === 1;
    }

    if (s1.slice(i1, i1 + length) === s2.slice(i2, i2 + length)) {
        memo[i1][i2][length] = 1;
        return true;
    }

    if (!checkIfSimilar(i1, i2, length, s1, s2)) {
        memo[i1][i2][length] = -1;
        return false;
    }

    for (let i = 1; i < length; ++i) {
        if (dfs(i1, i2, i, s1, s2, memo) && dfs(i1 + i, i2 + i, length - i, s1, s2, memo)) {
            memo[i1][i2][length] = 1;
            return true;
        }
        if (dfs(i1, i2 + length - i, i, s1, s2, memo) && dfs(i1 + i, i2, length - i, s1, s2, memo)) {
            memo[i1][i2][length] = 1;
            return true;
        }
    }

    memo[i1][i2][length] = -1;
    return false;
}

const checkIfSimilar = function(i1, i2, length, s1, s2) {
    const freq = new Map();
    for (let i = i1; i < i1 + length; ++i) {
        const c = s1[i];
        freq.set(c, (freq.get(c) || 0) + 1);
    }
    for (let i = i2; i < i2 + length; ++i) {
        const c = s2[i];
        freq.set(c, (freq.get(c) || 0) - 1);
    }
    for (const value of freq.values()) {
        if (value !== 0) {
            return false;
        }
    }
    return true;
}

记忆化搜索和动态规划

应该说记忆化搜索算法是自顶向下的，动态规划算法是自底向上的，二者都是动态规划算法思想的一种实现。

所以二者的使用条件是相同的，具体可以去看我的另一篇博客：https://sunra.top/posts/f7e2a78f/

理论上动态规划算法是某些记忆化搜索的更进一步，也就是说理论上，所有的DP算法都可以写成记忆化搜索。