Memory Search

Posted on Edited on In Waline:

Today’s leetcode daily question is a question about memory search. Here is a brief record.

This is the title link: https://leetcode-cn.com/problems/scramble-string/

To understand this, we must first understand what search is.

Search is familiar to everyone, DFS, BFS, depth-first search, and breadth-first search.

What is memory search? It is in this recursion search process, for some repeated sub-problems, find a data structure to record the results of the last calculation.

Does it sound a bit like Dynamic Programming?

Yes, the memory search is recursion, from top to bottom, while Dynamic Programming extracts the recursion process into state transition equations, memorizes the data structure into DP arrays, and then calculates from bottom to top.

Problem-solving ideas

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

Code implementation

We can write ordinary DFS first, and then add some data structure to remember existing results to prevent repeated calculations

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 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);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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;
}

Memory Search and Dynamic Programming

It should be said that the memory search algorithm is top-down, and the Dynamic Programming algorithm is bottom-up. Both are implementations of the idea of Dynamic Programming algorithm.

So the conditions of use of the two are the same, you can see my other blog for details: https://sunra.top/posts/f7e2a78f/

In theory, Dynamic Programming algorithm is a further step of some memory search, that is to say, in theory, all DP algorithms can be written as memory search.