# Backpack I&II

## – different sizes same price, ask maximum solution with fixed bag size

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

Example

If we have `4` items with size `[2, 3, 5, 7]`, the backpack size is 11, we can select `[2, 3, 5]`, so that the max size we can fill this backpack is `10`. If the backpack size is `12`. we can select `[2, 3, 7]` so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Note

You can not divide any item into small pieces.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

### Solution 1: DP – O(nm) time and O(nm) memory

state: f[i][j] = “前i”个数，取出一些组成和为<=j的最大值

function: f[i][j] = f[i-1][j – a[i]] + a[i] //取a[i]的情况

o f[i-1][j] //不取a[i]的情况

```public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
int[][] backPack = new int[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
backPack[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
backPack[0][j] = 0;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
//doesn't contain A[i]
backPack[i][j] = backPack[i - 1][j];
//contains A[i]
if (j >= A[i - 1]) {
backPack[i][j] = Math.max(backPack[i][j], backPack[i - 1][j - A[i - 1]] + A[i - 1]);
}
if (backPack[i][j] > max) {
max = backPack[i][j];
}
}
}
return max;
}```

### Solution 2. O(mn) time O(n) space, 利用行数取模优化空间 rolling array

```public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
int[][] backPack = new int[2][m + 1];
for (int i = 0; i < 2; i++) {
backPack[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
backPack[0][j] = 0;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
//doesn't contain A[i]
backPack[i % 2][j] = backPack[(i - 1) % 2][j];
//contains A[i]
if (j >= A[i - 1]) {
backPack[i % 2][j] = Math.max(backPack[i % 2][j], backPack[(i - 1) % 2][j - A[i - 1]] + A[i - 1]);
}
if (backPack[i % 2][j] > max) {
max = backPack[i % 2][j];
}
}
}
return max;
}```

### Solution 3: dp

f[i][j] = 前i个item能不能正好组成j

f[i][j] = f[i-1][j-a[i]] //取a[i]

f[i-1][j] //不取a[i]

return max j which f[i][j] == true

```public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
boolean[][] backPack = new boolean[A.length + 1][m + 1];
backPack[0][0] = true;
for (int i = 1; i <= A.length; i++) {
backPack[i][0] = true;
}
for (int j = 1; j <= m; j++) {
backPack[0][j] = false;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
backPack[i][j] = backPack[i - 1][j];
if (j >= A[i - 1]) {
backPack[i][j] |= backPack[i - 1][j - A[i - 1]];
}
if (backPack[i][j]) {
max = j;
}
}
}
return max;
}```

## – different size and price, ask for maximum value with fixed bag size

### Solution 1. O(m*n) time, O(m*n) space

f[i][j]:maximum value with first i items in A with a m sized bag

f[i][j] = f[i-1][j – a[i]] + v[i] //取a[i]的情况

= f[i-1][j] //不取a[i]的情况

```public int backPackII(int m, int[] A, int V[]) {
if (A == null || V == null || m <= 0) {
return 0;
}
int[][] maxValue = new int[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
maxValue[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
maxValue[0][j] = 0;
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
maxValue[i][j] = maxValue[i - 1][j];
if (j >= A[i - 1]) {
maxValue[i][j] = Math.max(maxValue[i][j], maxValue[i - 1][j - A[i - 1]] + V[i - 1]);
}
}
}
return maxValue[A.length][m];
}```

### Solution 2: O(m*n) time, O(m) space

```public int backPackII(int m, int[] A, int V[]) {
if (A == null || V == null || m <= 0) {
return 0;
}
int[][] maxValue = new int[2][m + 1];
for (int i = 0; i < 2; i++) {
maxValue[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
maxValue[0][j] = 0;
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
maxValue[i % 2][j] = maxValue[(i - 1) % 2][j];
if (j >= A[i - 1]) {
maxValue[i % 2][j] = Math.max(maxValue[i % 2][j], maxValue[(i - 1) % 2][j - A[i - 1]] + V[i - 1]);
}
}
}
return maxValue[A.length % 2][m];
}```
Share

# Wildcard Matching

Implement wildcard pattern matching with support for `'?'` and `'*'`.

• `'?'` Matches any single character.
• `'*'` Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example
```<code>isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false</code>```

Solution1. Dynamic Programming

isMatch[i][j] = if first i chars for s can match first j chars of p

j==’*’: OR(isMatch[0~i][j-1])

j==’?’: isMatch[i-1][j-1]

else: isMatch[i-1][j-1] && s.charAt(i-1)==p.charAt(j-1)

```public boolean isMatch(String s, String p) {
//dp version
if (s == null || p == null) {
return false;
}
boolean[][] isMatch = new boolean[s.length() + 1][p.length() + 1];
isMatch[0][0] = true;
for (int i = 1; i <= s.length(); i++) {
isMatch[i][0] = false;
}
for (int j = 1; j <= p.length(); j++) {
isMatch[0][j] = isMatch[0][j - 1] && p.charAt(j - 1) == '*';
}
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == '*') {
for (int k = 0; k <= i; k++) {
if (isMatch[k][j - 1]) {
isMatch[i][j] = true;
break;
}
}
} else if (p.charAt(j - 1) == '?') {
isMatch[i][j] = isMatch[i - 1][j - 1];
} else {
isMatch[i][j] = isMatch[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1);
}
}
}
return isMatch[s.length()][p.length()];
}```

# Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example

For s1 = `"aabcc"`, s2 = `"dbbca"`

• When s3 = `"aadbbcbcac"`, return `true`.
• When s3 = `"aadbbbaccc"`, return `false`.

Solution: Dynamic Programming
isInterleave[i][j] = if first i chars of s1 and first j chars of s2 is interleave of first i+j chars of s3
isInterleave[i][j] = isInterleave[i – 1][j] && s1.charAt(i – 1) == s3.charAt(i + j – 1))
|| (isInterleave[i][j – 1] && s2.charAt(j – 1) == s3.charAt(i + j – 1))

```public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s3 == null
|| s1.length() + s2.length() != s3.length()) {
return false;
}
//isInterleave[i][j] = if first i chars of s1 and first j chars of s2
//is interleave of first i+j chars of s3
boolean[][] isInterleave = new boolean[s1.length() + 1][s2.length() + 1];
isInterleave[0][0] = true;
for (int i = 1; i <= s1.length(); i++) {
isInterleave[i][0] = isInterleave[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
}
for (int j = 1; j <= s2.length(); j++) {
isInterleave[0][j] = isInterleave[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
}
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
isInterleave[i][j] = (isInterleave[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
|| (isInterleave[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
}
}
return isInterleave[s1.length()][s2.length()];
}```