记录

sicilianee 发表于 2018-5-29 07:56
0528 1. Word Break II

// 超时。为什么？loop本身已经是cubic complexity, 而每次loop中要loop之前的an ...

降维，复杂度应该降了不少。string的问题如果start和end中有一个是固定的，那就不是二维而是一维dp了
真实复杂度是exponential，因为res是exponential。
虽然test case给出的两个极端情况不可分，但是由于子问题可分，子问题的res是exponential，而用dp必须先解答子问题，因此跑的过程中还是会超时。2**n

而dfs with memoization 的话因为是top down，在解决父问题的过程中遇到了子问题才去解决子问题，因此
如果根本没有有效解，是不会算到每一个子问题的。因此在这种特殊的情况下， 他的剪枝要比dp更多。能通过。

// n**2 * O(max(res) in the middle of computation) version, should still TLE

/**
* @param {string} s
* @param {string[]} wordDict
* @return {string[]}
*/
var wordBreak = function(s, wordDict) {
  const len = s.length
  const dp = Array(len).fill(null)
  const set = new Set(wordDict)
  for (let i = len - 1; i >= 0; i--) {
    const res = []
    const full = s.slice(i)
    if (set.has(full)) {
      res.push(full)
    }
    // now loop left, break down right
    for (j = i; j < len - 1; j++) {
      const leftStr = s.slice(i, j + 1)
      const right = dp[j + 1]
      if (set.has(leftStr) && right) {
        right.forEach(rightStr => {
          res.push(`${leftStr} ${rightStr}`)
        })
      }
    }
    if (res.length > 0) {
      dp[i] = res
    }
  }
  return dp[0] ? dp[0] : []
};


// ---- test

const a = "aaaaaaaaaaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
console.log(a.length)
const b = ["aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa","ba"]
console.log(wordBreak(a, b))

console.log(wordBreak('catsanddog', ["cat", "cats", "and", "sand", "dog"]).length === 2)
console.log(wordBreak('pineapplepenapple', ["apple", "pen", "applepen", "pine", "pineapple"]).length === 3)
console.log(wordBreak('catsandog',  ["cats", "dog", "sand", "and", "cat"]).length === 0)

sicilianee 发表于 2018-5-29 08:32
降维，复杂度应该降了不少。string的问题如果start和end中有一个是固定的，那就不是二维而是一维dp了
真 ...

第一个dp最fragile
第二个dp可以防止invalid点在最后的情况，但是不能防止在前面或者中间
而dfs之所以immune to all positions of invalid point is because it has two conditions:
it checks both the leftStr and the right part array.
The subproblem is the right part array, but we need to combine the left part to make it work.
In a dp solution, we focus totally on the sub problem, ignoring the possible left constraint.
In dfs, if leftStr is not valid, we won't go further to solve the subproblem.

If the invalid point exists in the subproblem, we'll go from top down, pre-order. Here is the thing:
each time we break a string down into 2 parts, left half as a literal string and right half treat as a subproblem.
Now the invalid point exists either in the leftStr or the right subproblem.
If the invalid point exists in the subproblem, in the extreme case in the smallest subproblem (far right), then there would be no intermediate answer that is very big (exponential) (except for the first dp where there are many smallest subproblems), so both dp and dfs can handle it.
If however the invalid point is not in the subproblem, in the leftStr, then dp would totally ignore it, but dfs would first check the leftStr, and won't go into the subproblem if the leftStr is invalid.

Now consider the invalid point is in the subproblem but not the smallest, we would go top down, pre-order. As soon as the leftStr part reached the invalid point, we stop going further down. And from that point up, all answers are empty so there won't be any big answer. So the solution won't explode if there is an invalid point in the string.
It will however if the res itself is big as exponential.

sicilianee 发表于 2018-5-29 08:59
第一个dp最fragile
第二个dp可以防止invalid点在最后的情况，但是不能防止在前面或者中间
而dfs之所以i ...

This is an interesting case:
In some cases of the input, dfs with memoization would run much faster than dp.

-- if input under certain conditions dfs would be asymptotically faster than dp.
So they are not exactly the same.

sicilianee 发表于 2018-5-29 09:03
This is an interesting case:
In some cases of the input, dfs with memoization would run much fast ...

But when this could happen we still don't have a general rule.

In this case: a condition followed by a subproblem, we test the condition and solve the subproblem in a dfs. In these cases dp might be slower for some input because it ignores the condition.

sicilianee 发表于 2018-5-29 09:05
But when this could happen we still don't have a general rule.

In this case: a condition follow ...

top down could detect and prune early one.
bottom up would not be able to do so.

Since dp is to solve the subproblems first, it is a bottom up solution. So there are less room for pruning.

Final version. In the end it becomes short and easy. Good one.


/**
* @param {string} s
* @param {string[]} wordDict
* @return {string[]}
*/
var wordBreak = function(s, wordDict) {
  const set = new Set(wordDict)
  const map = new Map()
  const len = s.length
  return breakWord(0)

  function breakWord (i) {
    if (map.has(i)) {
      return map.get(i)
    }
    const res = []
    if (set.has(s.slice(i))) {
      res.push(s.slice(i))
    }
    for (let j = i; j < len - 1; j++) {
      const leftStr = s.slice(i, j + 1)
      if (set.has(leftStr)) {
        const right = breakWord(j + 1)
        right.forEach(rightStr => {
          res.push(`${leftStr} ${rightStr}`)
        })
      }
    }
    map.set(i, res)
    return res
  }
};

0528 2. Max Chunks To Make Sorted II


/**
* @param {number[]} arr
* @return {number}
*/
var maxChunksToSorted = function(arr) {
  arr = arr.map((val, index) => [index, val])
  // !!! this sort needs to be stable, while quicksort is not stable
  arr.sort(([index1, val1], [index2, val2]) => {
    return val1 === val2
      ? index1 - index2
      : val1 - val2
  })
  arr = arr.map(([index], newIndex) => [Math.min(index, newIndex), Math.max(index, newIndex)])
  arr.sort(([start1], [start2]) => start1 - start2)
  // now merge intervals
  const res = []
  for (let i = 0; i < arr.length; i++) {
    const curr = arr[i]
    const top = res[res.length - 1]
    if (res.length > 0 && top[1] >= curr[0]) { // merge
      top[1] = Math.max(top[1], curr[1])
    } else {
      res.push(curr)
    }
  }
  return res.length
};

console.log(maxChunksToSorted([5,4,3,2,1]) === 1)
console.log(maxChunksToSorted([2,1,3,4,4]) === 4)
console.log(maxChunksToSorted([0,1,1,1,0,0,0,0,1,1,0]) === 2)

sicilianee 发表于 2018-5-29 11:29
0528 2. Max Chunks To Make Sorted II

O(n) solution. NiuBi

Note that rightMin is exclusive. Or like what they do you shift one position when you calc count.

/**
* @param {number[]} arr
* @return {number}
*/
var maxChunksToSorted = function(arr) {
  arr = arr.map((val, index) => [index, val])
  // !!! this sort needs to be stable, while quicksort is not stable
  arr.sort(([index1, val1], [index2, val2]) => {
    return val1 === val2
      ? index1 - index2
      : val1 - val2
  })
  arr = arr.map(([index], newIndex) => [Math.min(index, newIndex), Math.max(index, newIndex)])
  arr.sort(([start1], [start2]) => start1 - start2)
  // now merge intervals
  const res = []
  for (let i = 0; i < arr.length; i++) {
    const curr = arr[i]
    const top = res[res.length - 1]
    if (res.length > 0 && top[1] >= curr[0]) { // merge
      top[1] = Math.max(top[1], curr[1])
    } else {
      res.push(curr)
    }
  }
  return res.length
};

// --- version 2

var maxChunksToSorted = function(arr) {
  // !!!! we will break on a position, not an element, so left inclusive and right exclusive
  // we start from cover the left, check when can we take left out as a new chunck
  const len = arr.length
  const leftMax = Array(len)
  const rightMin = Array(len)
  // inclusive
  let max = -Infinity
  for (let i = 0; i < len; i++) {
    max = Math.max(max, arr[i])
    leftMax[i] = max
  }
  // !!! exclusive
  let min = Infinity
  rightMin[len - 1] = Infinity
  for (i = len - 2; i >= 0; i--) {
    min = Math.min(min, arr[i + 1])
    rightMin[i] = min
  }
  let count = 0
  for (let i = 0; i < len; i++) {
    if (leftMax[i] <= rightMin[i]) {
      count++
    }
  }
  return count
};

0528 3.  Student Attendance Record II

Memory Limit Exceeded

/**
* @param {number} n
* @return {number}
*/
var checkRecord = function(n) {
  // convert from the recursion signature to a dp deduction formula
  const mod = Math.pow(10, 9) + 7
  // !!! still 6 states not 4, the yes means has used so far, not only use in this cell
  // one is so far all, one is so far continuous, shit very confusing
  const dp = Array(n + 1).fill()
    .map(() => Array(2).fill()
      .map(() => Array(3).fill(0)))
  // !!! must init 1, cannot rely on 0 or you get all 0
  const one = dp[1]
  one[1][0] = 1 // a
  one[0][1] = 1 // l
  one[0][0] = 1 // p
  for (let i = 2; i <= n; i++) {
    const curr = dp[i]
    const prev = dp[i - 1]
    curr[0][0] = (prev[0][0] + prev[0][1] + prev[0][2]) % mod
    curr[0][1] = prev[0][0] % mod
    curr[0][2] = prev[0][1] % mod
    curr[1][0] = (prev[0][0] + prev[0][1] + prev[0][2]
                  + prev[1][0] + prev[1][1] + prev[1][2]) % mod
    curr[1][1] = prev[1][0] % mod
    curr[1][2] = prev[1][1] % mod
  }
  const not = dp[n][0]
  const yes = dp[n][1]
  let count = 0
  for (let i = 0; i < 3; i++) {
    count = (count + (not[i] + yes[i]) % mod) % mod
  }
  return count
};

sicilianee 发表于 2018-5-29 13:01
0528 3.  Student Attendance Record II

Memory Limit Exceeded

Since each dp only depends on previous dp, we could just use some vars and drop the dp array.

Quite interesting but error prone.

/**
* @param {number} n
* @return {number}
*/
var checkRecord = function(n) {
  // convert from the recursion signature to a dp deduction formula
  const mod = Math.pow(10, 9) + 7
  // !!! 1. still 6 states not 4, the yes means has used so far, not only use in this cell
  // one is so far all, one is so far continuous, shit very confusing
  // !!! 2. the initial dp got MLE. Since dp cell only depends on previous, we could turn
  // memory into constant

  // a, l, p, i = 1
  let yes_0 = 1, no_1 = 1, no_0 = 1, yes_1 = 0, yes_2 = 0, no_2 = 0
  for (let i = 2; i <= n; i++) {
    ;[
      yes_0,
      yes_1,
      yes_2,
      no_0,
      no_1,
      no_2
    ] = [
      (no_0 + no_1 + no_2 + yes_0 + yes_1 + yes_2) % mod,
      yes_0,
      yes_1,
      (no_0 + no_1 + no_2) % mod,
      no_0,
      no_1
    ]
  }
  return (yes_0 + yes_1 + yes_2 + no_0 + no_1 + no_2) % mod
};