403. Frog Jump

In first place, the solution can be done by recursion and is very straightforward. The tricky part is in line 9 because when gap is less than k, the frog has to jump over the stone as it only has choices of k-1, k and k+1.

1:  class Solution {  
2:  public:  
3:    bool canCross(vector<int>& stones) {  
4:      return canJump(stones, 0, 0);  
5:    }  
6:    bool canJump(vector<int> &stones, int pos, int k) {  
7:      for (int i = pos+1; i < stones.size(); i++) {  
8:        int gap = stones[i] - stones[pos];  
9:        if (gap < k - 1) continue; // the frog has to jump over the stone.  
10:        if (gap > k + 1) return false;  
11:        if (canJump(stones, i, gap, dp)) return true;  
12:      }  
13:      return pos == stones.size()-1;  
14:    }  
15:  };  

However, this solution gets TLE. So the memorization is used.

1:  class Solution {  
2:  public:  
3:    bool canCross(vector<int>& stones) {  
4:      set<pair<int,int>> dp;  
5:      return canJump(stones, 0, 0, dp);  
6:    }  
7:    bool canJump(vector<int> &stones, int pos, int k, set<pair<int,int>> &dp) {  
8:      if (dp.count(make_pair(pos, k))) return false;  
9:      for (int i = pos+1; i < stones.size(); i++) {  
10:        int gap = stones[i] - stones[pos];  
11:        if (gap < k - 1) continue; // the frog has to jump over the stone.  
12:        if (gap > k + 1) { dp.insert(make_pair(pos, k)); return false; }  
13:        if (canJump(stones, i, gap, dp)) { dp.insert(make_pair(pos, k)); return true; }  
14:      }  
15:      return pos == stones.size()-1;  
16:    }  
17:  };  

63. Unique Paths II

Same solution with problem “62. Unique Paths”. The only difference is the initial state.

1:  class Solution {  
2:  public:  
3:    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {  
4:      int rows = obstacleGrid.size();  
5:      if (rows == 0) return 0;  
6:      int cols = obstacleGrid[0].size();  
7:      vector<vector<int>> dp(rows, vector<int>(cols, 0));  
8:      for (int j = 0; j < cols; j++) {  
9:        if (obstacleGrid[0][j] == 1) break;  
10:        dp[0][j] = 1;  
11:      }  
12:      for (int i = 0; i < rows; i++) {  
13:        if (obstacleGrid[i][0] == 1) break;  
14:        dp[i][0] = 1;  
15:      }  
16:      for (int i = 1; i < rows; i++) {  
17:        for (int j = 1; j < cols; j++) {  
18:          if (obstacleGrid[i][j] == 0) {  
19:            dp[i][j] = dp[i-1][j]+dp[i][j-1];  
20:          }  
21:        }  
22:      }  
23:      return dp[rows-1][cols-1];  
24:    }  
25:  };  

198. House Robber

Let dp[i] be the maximal treasure the thief can steel in house i. So the state transition is dp[i] = max(dp[i-1], nums[i-2]+nums[i]). The initial state will be dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

1:  class Solution {  
2:  public:  
3:    int rob(vector<int>& nums) {  
4:      int n = nums.size();  
5:      if (n == 0) return 0;  
6:      if (n == 1) return nums[0];  
7:      if (n == 2) return max(nums[0], nums[1]);  
8:      vector<int> dp(n, 0);  
9:      dp[0] = nums[0];  
10:      dp[1] = max(nums[0], nums[1]);  
11:      for (int i = 2; i < n; i++) {  
12:        dp[i] = max(dp[i-1], dp[i-2]+nums[i]);  
13:      }  
14:      return dp[n-1];  
15:    }  
16:  };  

376. Wiggle Subsequence

I was trapped in finding a DP solution that dp[i] means the longest wiggle subsequence so far at index i. However, I then realized two things: 1. The wiggle subsequence is not necessary to be consecutive; 2. [2,1] is a wiggle and [1,2] is a wiggle too. So I can’t solve it by something like Kadane’s algorithm. I followed the top rated solution which uses two dp arrays and runs at O(n^2) because subsequence is not required to be consecutive.

1:  class Solution {  
2:  public:  
3:    int wiggleMaxLength(vector<int>& nums) {  
4:      if (nums.size() < 2) return nums.size();  
5:      vector<int> large(nums.size(), 1);  
6:      vector<int> small(nums.size(), 1);  
7:      for (int i = 1; i < nums.size(); i++) {  
8:        for (int j = i-1; j >= 0; j--) {  
9:          if (nums[i] > nums[j]) large[i] = max(large[i], small[j]+1);  
10:          else if (nums[i] < nums[j]) small[i] = max(small[i], large[j]+1);  
11:        }  
12:      }  
13:      return max(small[nums.size()-1], large[nums.size()-1]);  
14:    }  
15:  };  

64. Minimum Path Sum

Let dp[i][j] to be the minimum path sum at (i, j), then the transition state is dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

1:  class Solution {  
2:  public:  
3:    int minPathSum(vector<vector<int>>& grid) {  
4:      int row = grid.size();  
5:      if (row == 0) return 0;  
6:      int col = grid[0].size();  
7:      for (int j = 1; j < col; j++) {  
8:        grid[0][j] += grid[0][j-1];  
9:      }  
10:      for (int i = 1; i < row; i++) {  
11:        grid[i][0] += grid[i-1][0];  
12:      }  
13:      for (int i = 1; i < row; i++) {  
14:        for (int j = 1; j < col; j++) {  
15:          grid[i][j] += min(grid[i-1][j], grid[i][j-1]);  
16:        }  
17:      }  
18:      return grid[row-1][col-1];  
19:    }  
20:  };  

62. Unique Paths

Let dp[i][j] is the maximum path at grid[i][j], so the transition statement is quite easy to achieve:
dp[i][j] = dp[i-1][j] + dp[i][j-1]. For the initial state, the first row and first column are initialized to all 1s.

1:  class Solution {  
2:  public:  
3:    int uniquePaths(int m, int n) {  
4:      vector<vector<int>> grid(m, vector<int>(n, 1));  
5:      for (int i = 1; i < m; i++) {  
6:        for (int j = 1; j < n; j++) {  
7:          grid[i][j] = grid[i-1][j] + grid[i][j-1];  
8:        }  
9:      }  
10:      return grid[m-1][n-1];  
11:    }  
12:  };  

325. Maximum Size Subarray Sum Equals k

When I saw this problem, my first impression is that it is similar to maximum subarray sum which can be solved by Kadane's algorithm. But this problem requires sum to be k. So, if we have sum[i] to be the sum from [0, i], the problem becomes to find all pairs of sum[i] == k or sum[i]-sum[j] == k. For sum[i] == k, the len is i+1, for sum[i]-sum[j] == k, the length is j - i. If we can save all sums before i in a hash table whose (key, value) pair is (sum, index), to get j which sum[i]-sum[j] == k, we only need to look up the hash table to see if sum[i]-k exists in it.

Note, since we scan from 0 to n, if sum[i] == k, the max length so far must be i+1. Also to avoid duplicates, we only save (sum, i) when this pair isn't existing in hash table. Why we don't have to save the pair (sum, j) later? Because we want to get the maximum size, the first pair guarantees it.

1:  class Solution {  
2:  public:  
3:    int maxSubArrayLen(vector<int>& nums, int k) {  
4:      unordered_map<int, int> mp;  
5:      int sum = 0, maxLen = 0;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        sum += nums[i];  
8:        if (k == sum) maxLen = i+1;  
9:        else if (mp.find(sum-k) != mp.end()) maxLen = max(maxLen, i-mp[sum-k]);  
10:        if (mp.find(sum) == mp.end()) mp[sum] = i;  
11:      }  
12:      return maxLen;  
13:    }  
14:  };  

343. Integer Break

Let's first look at the case where an integer can be broken into two integers, so the product  = x(N-x). The maximal product is at x=N/2. Now let's see what integers need to break in order to achieve the largest product, i.e. (N/2)*(N/2) >= N => N >= 4. So the product must consists of factors that can't be broken. The largest non-break number is 3. However, there is a special case where 4 should be broken into 2*2 not 1*3. So the solution is as following in which line 8 and 12 take care of the special case.

1:  class Solution {  
2:  public:  
3:    int integerBreak(int n) {  
4:      if (n == 1) return 1;  
5:      if (n == 2) return 1;  
6:      if (n == 3) return 2;  
7:      int product = 1;  
8:      while (n > 4) {  
9:        product *= 3;  
10:        n -= 3;  
11:      }  
12:      product *= n;  
13:      return product;  
14:    }  
15:  };  

256. Paint House

Let costs[i][0] be the minimal cost for painting house i red, so we have costs[i][0] += min(costs[i-1][1], costs[i-1][2]). Same to blue and green.

1:  class Solution {  
2:  public:  
3:    int minCost(vector<vector<int>>& costs) {  
4:      int n = costs.size();  
5:      for (int i = 1; i < n; i++) {  
6:        costs[i][0] += min(costs[i-1][1], costs[i-1][2]);  
7:        costs[i][1] += min(costs[i-1][0], costs[i-1][2]);  
8:        costs[i][2] += min(costs[i-1][0], costs[i-1][1]);  
9:      }  
10:      return n == 0 ? 0 : min(costs[n-1][0], min(costs[n-1][1], costs[n-1][2]));  
11:    }  
12:  };  

338. Counting Bits

My intuition is to count bits for each number. So the total run time is O(32*n). However, if we look at binary representation closely,  "0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111", we'll see that once we reach a multiple of 2 say 2^n, its right bits just repeat all the numbers from 0 to 2^n-1. So we can program dynamically.

1:  class Solution {  
2:  public:  
3:    vector<int> countBits(int num) {  
4:      int shift = 0;  
5:      vector<int> res(num+1, 0);  
6:      int i = 1, j = 0;  
7:      while (i <= num) {  
8:        for (int j = 0; i <= num && j <(1<<shift); i++,j++) {  
9:          res[i] = res[j]+1;  
10:        }  
11:        shift++;  
12:      }  
13:      return res;  
14:    }  
15:  };  

322. Coin Change

This is a classic dynamic programming problem. If you don't know the problem before, it will be tricky. Let dp[i] be the minimal change for amount i. We should try from 1 to the target amount such that should a coin amount be less or equal to i, dp[i] = min(dp[i], dp[i-coins[j]]+1), i.e. the minimal change for amount i will be the minimal change at i-coins[j] plus 1.

1:  class Solution {  
2:  public:  
3:    int coinChange(vector<int>& coins, int amount) {  
4:      vector<int> dp(amount+1, INT_MAX-1);  
5:      dp[0] = 0;  
6:      for (int i = 1; i <= amount; i++) {  
7:        for (int j = 0; j < coins.size(); j++) {  
8:          if (coins[j] <= i) {  
9:            dp[i] = min(dp[i], dp[i-coins[j]]+1);  
10:          }  
11:        }  
12:      }  
13:      return dp[amount] == INT_MAX-1 ? -1 : dp[amount];  
14:    }  
15:  };  

377. Combination Sum IV

I don’t have any clue when I first saw this problem. I followed the top rated solution. The solution has similary idea with problem "322. Coin Change". The idea is to let dp[i] to be the maximal combinations for target i. Note only when nums[j] <= target, nums[j] is a candidate for the combination and the number of combinations with this candidate nums[j] is dp[target-nums[j]]. And also for the target, we need to sum up all the combinations with candidates nums[j] less or equal than the target, so we have
dp[i] = sum of dp[i-nums[j]] where nums[j] <= i.

1:  class Solution {  
2:  public:  
3:    int combinationSum4(vector<int>& nums, int target) {  
4:      vector<int> res(target+1, 0);  
5:      dp[0] = 1;  
6:      for (int i = 1; i <= target; i++) {  
7:        for (int j = 0; j < nums.size(); j++) {  
8:          if (nums[j] <= i) dp[i] += dp[i-nums[j]];  
9:        }  
10:      }  
11:      return dp[target];  
12:    }  
13:  };  

204. Count Primes

This is a dynamic problem. The minimal prime is 2. So we can start from 2 and we know that any multiple of 2 is a prime. So we mark off all multiple of 2. Then we check 3. Similarly, and multiple of 3 is not a prime so we mark off them. Now we come to 4. Since 4 is a multiple of 2 and has been marked off, we just ignore and continue to 5. Note, we don't have to start from 5*2 because 5*2, 5*3, 5*4 have all been marked off before. So we can start from 5*5. Therefore, the algorithm is as following:

1:  class Solution {  
2:  public:  
3:    int countPrimes(int n) {  
4:      vector<bool> isPrime(n, true);  
5:      for (int i = 2; i*i < n; i++) {  
6:        if (!isPrime[i]) continue;  
7:        for (int j = i*i; j < n; j += i) {  
8:          isPrime[j] = false;  
9:        }  
10:      }  
11:      int count = 0;  
12:      for (int i = 2; i < n; i++) {  
13:        if (isPrime[i]) count++;  
14:      }  
15:      return count;  
16:    }  
17:  };  

121. Best Time to Buy and Sell Stock

This is actually a maximum subarray sum problem which can be solved by Kadane’s Algorithm.
Here is a very good video explaining this algorithm:
https://www.youtube.com/watch?v=86CQq3pKSUw

1:  class Solution {  
2:  public:  
3:    int maxProfit(vector<int>& prices) {  
4:      int maxGlobal = 0;  
5:      int maxCurrent = 0;  
6:      for (int i = 1; i < prices.size(); i++) {  
7:        maxCurrent = max(prices[i]-prices[i-1], maxCurrent + prices[i]-prices[i-1]);  
8:        if (maxCurrent > maxGlobal) maxGlobal = maxCurrent;  
9:      }  
10:      return maxGlobal;  
11:    }  
12:  };  

140. Word Break II

My intuition is to use backtracking solution directly. But it get TLE. So we definitely need to do some memorization.

1:  class Solution {  
2:  public:  
3:    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {  
4:      vector<string> res;  
5:      helper(s, 0, wordDict, "", res);  
6:      return res;  
7:    }  
8:    void helper(string s, int i, unordered_set<string> &wordDict, string sol, vector<string> &res) {  
9:      if (i == s.size()) { sol.pop_back(); res.push_back(sol); return;}  
10:      for (int j = i; j < s.size(); j++) {  
11:        string word = s.substr(i, j-i+1);  
12:        if (wordDict.count(word) == 0) continue;  
13:        helper(s, j+1, wordDict, sol+word+" ", res);  
14:      }  
15:    }  
16:  };  

Let’s look at one example first. Say, we have string “aaaab”, dictionary [“a”, “aa”]. Then let’s see how the solution above works.
Step 1: “a a a a” and “b” not valid.
Setp 2: “a a a” and recursively check “ab”.
Step 3: “a a aa” and “b” not valid.
Step 4: “a a” and recursively check “aab”.
Step 5: “a aa” and recursively check “ab”.
Step 6: “aa” and recursively check “aab”.
From here, we can see in Step 5 we don’t have to recursively check “ab” again because from Step 2 we already know that “ab” is not breakable. Same to Step 6. So if we can memorize if word[i..n-1] is breakable, then we can speed up the solution. Let dp[i] be that s[i..n-1] is not breakable. And then the trick becomes how to update the dp[i]. If there is no breakable words, no new solution will be added to the result. So we can update the dp[i] upon that.

1:  class Solution {  
2:  private:  
3:    vector<bool> dp;  
4:  public:  
5:    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {  
6:      vector<string> res;  
7:      dp = vector<bool>(s.size(), true);  
8:      helper(s, 0, wordDict, "", res);  
9:      return res;  
10:    }  
11:    void helper(string s, int i, unordered_set<string> &wordDict, string sol, vector<string> &res) {  
12:      if (i == s.size()) { sol.pop_back(); res.push_back(sol); return;}  
13:      for (int j = i; j < s.size(); j++) {  
14:        string word = s.substr(i, j-i+1);  
15:        int res_sz = res.size();  
16:        if (wordDict.count(word) == 0 || !dp[j]) continue;  
17:        helper(s, j+1, wordDict, sol+word+" ", res);  
18:        if (res_sz == res.size()) dp[j] = false;  
19:      }  
20:    }  
21:  };  

370. Range Addition

I implemented in a naive way. But it got TLE.

1:  class Solution {  
2:  public:  
3:    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {  
4:      vector<int> res(length, 0);  
5:      for (int i = 0; i < updates.size(); i++) {  
6:        for (int j = updates[i][0]; j <= updates[i][1]; j++) {  
7:          res[j] += updates[i][2];  
8:        }  
9:      }  
10:      return res;  
11:    }  
12:  };  

The hits provides a O(n+k) running time solution. Let's see the example. Given length = 5.
update(1,3,2), we should have [0, 2, 2, 2, 0]. What if we only record two positions? It means we need to do sum from the left to right to get the new array. So we can modify the array to be [0, 2, 0, 0, -2] and when we do sum from left to right, i.e. res[i] = res[i] + res[i-1], we'll get [0, 2, 2, 2, 0] which is exactly the same as our expected array. So for each update(i, j, a), we add a to res[i] and subtract a from res[j+1]. In the end, we sum up the res from left to right following res[i] = res[i] + res[i-1].

1:  class Solution {  
2:  public:  
3:    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {  
4:      vector<int> res(length+1, 0);  
5:      for (int i = 0; i < updates.size(); i++) {  
6:        res[updates[i][0]] += updates[i][2];  
7:        res[updates[i][1]+1] -= updates[i][2];  
8:      }  
9:      for (int i = 1; i < length; i++) {  
10:        res[i] = res[i]+res[i-1];  
11:      }  
12:      res.pop_back();  
13:      return res;  
14:    }  
15:  };  

368. Largest Divisible Subset

I don't have any clue to solve this problem. I followed one of the top voted solutions. The trick here is for a new integer I, it can be placed into the set as long as it divides the smallest number in the set or it can be divided by the largest number in the set. Also for the numbers in the same subset, we use union find solution.
Let T[n] be the size of the largest divisible subset whose largest number is nums[n].
Let child[n] be the index of its child in the nums[n].
Now let's look at an example, nums = [1,2,3,4].
i = 0, j = 0, T = [1,0,0,0] child=[0,0,0,0]
i = 1, j = 1, T = [1,1,0,0] child=[0,1,0,0]
         j = 0, T = [1,2,0,0] child=[0,0,0,0] (2's child is 1)
i = 2, j = 2, T = [1,2,1,0] child=[0,1,2,0]
         j = 1, 3 can't be divided by 2, nothing to change
         j = 0, T = [1,2,2,0] child=[0,0,0,0] (3's child is 1)
i = 3, j = 3, T = [1,2,2,1] child=[0,1,2,3]
         j = 2, 4 can't be divided by 3, nothing to change
         j = 1, T = [1,2,2,3] child=[0,1,2,1] (4's child is 2)
So far, the longest subset is 3. And we can find these three numbers by chasing the child[] array, i.e. nums[3]->nums[1]->nums[0] (i.e. 4,2,1). Therefore, in order to get the largest divisible subset, we can maintain the largest size of the subsets and the largest number's index in the set. The subset can be achieved by chasing the child[] array.

1:  class Solution {  
2:  public:  
3:    vector<int> largestDivisibleSubset(vector<int>& nums) {  
4:      vector<int> res;  
5:      if (nums.size() == 0) return res;  
6:      vector<int> T(nums.size(), 0);  
7:      vector<int> child(nums.size(), 0);  
8:      int m = 0, mi = 0;  
9:      sort(nums.begin(), nums.end());  
10:      for (int i = 0; i < nums.size(); i++) {  
11:        for (int j = i; j >= 0; j--) {  
12:          if (nums[i] % nums[j] == 0 && T[j] + 1 > T[i]) {  
13:            T[i] = T[j] + 1;  
14:            child[i] = j;  
15:          }  
16:          if (T[i] > m) {  
17:            m = T[i];  
18:            mi = i;  
19:          }  
20:        }  
21:      }  
22:      for (int i = 0; i < m; i++) {  
23:        res.push_back(nums[mi]);  
24:        mi = child[mi];  
25:      }  
26:      return res;  
27:    }  
28:  };  

375. Guess Number Higher or Lower II

Let dp[i][j] be the minimum cost among  [i...j] on worst cases. So, To compute dp[i][j], we need to traverse every number among [i...j] for worst cases cost and select the minimum cost among these worst cases.
To compute worst case for k in [i...j], we have worst = (k + max(dp[i][k-1], dp[k+1][j])).
To get the minimum cost among [i...j], we just pick the choose min(cost, worst) for each worst.

1:  class Solution {  
2:  public:  
3:    int getMoneyAmount(int n) {  
4:      vector<vector<int>> dp(n+1, vector<int>(n+1, 0));  
5:      return helper(dp, 1, n);  
6:    }  
7:    int helper(vector<vector<int>> &dp, int s, int e) {  
8:      if (s >= e) return 0;  
9:      if (dp[s][e] != 0) return dp[s][e];  
10:      int cost = INT_MAX;  
11:      for (int i = s; i <= e; i++) {  
12:        int worst = i + max(helper(dp, s, i-1), helper(dp, i+1, e));  
13:        cost = min(cost, worst);  
14:      }  
15:      dp[s][e] = cost;  
16:      return cost;  
17:    }  
18:  };  

276. Paint Fence

When there is only one fence, we have total k ways to paint.
When there is two fence, for the second fence, we can paint the same color with the first one and the total ways to paint these two posts is k. OR we can paint the different color and the total ways to paint these two posts is k*(k-1). If we can keep the total ways to paint ith post, then the ways for ith post is
Case 1: i-1 and i-2 have the same color, then the ways to paint is (k-1) * dp[i-2]
Case 2: i-1 and i-2 have different colors, then the ways to paint is (k-1) * dp[i-1]
So the dp[i] = (dp[i-2] + dp[i-1])*(k-1);

1:  class Solution {  
2:  public:  
3:    int numWays(int n, int k) {  
4:      if (n == 0) return 0;  
5:      if (n == 1) return k;  
6:      vector<int> dp(n, 0);  
7:      dp[0] = k;  
8:      dp[1] = k+k*(k-1);  
9:      for (int i = 2; i < n; i++) {  
10:        dp[i] = (dp[i-1] + dp[i-2]) * (k-1);  
11:      }  
12:      return dp[n-1];  
13:    }  
14:  };  

Also, this DP solution can be optimized to have O(1) space because we only care about previous two states.

1:  class Solution {  
2:  public:  
3:    int numWays(int n, int k) {  
4:      if (n == 0) return 0;  
5:      if (n == 1) return k;  
6:      int n_2 = k, n_1 = k*(k-1);  
7:      for (int i = 2; i < n; i++) {  
8:        int tmp = n_1;  
9:        n_1 = (n_2 + n_1) * (k-1);  
10:        n_2 = tmp;  
11:      }  
12:      return n_2 + n_1;  
13:    }  
14:  };  

361. Bomb Enemy

Let count[i][j] be the maximum enemies that a bomb can kill in row i, col j. The naive solution will run O(m*n*(m+n)) time. The trick here to make it O(mn) is to keep a head and a tail variables. The head variable keeps the maximum enemies from left to grid[i][j] and the tail variable keeps the maximum enemies from the right to grid[i][j]. So for count[i][j], we want to add head if grid[i][j] is empty, i.e. grid[i][j] == 0 and for count[i][col-1-j], we want to add tail if grid[i][col-1-j] is empty. So when we traverse the row from 0 to col, we actually computes the maximum enemies for every position. Same for scanning columns. head is incremented by 1 if it finds an enemy or becomes 0 if it finds a wall. Same for tail.

1:  class Solution {  
2:  public:  
3:    int maxKilledEnemies(vector<vector<char>>& grid) {  
4:      int row = grid.size();  
5:      if (row == 0) return 0;  
6:      int col = grid[0].size();  
7:      vector<vector<int>> count(row, vector<int>(col, 0));  
8:      int i = 0, j = 0, head = 0, tail = 0;  
9:      for (i = 0; i < row; i++) {  
10:        for (j = head = tail = 0; j < col; j++) {  
11:          count[i][j] = grid[i][j] != '0' ? 0 : (count[i][j] + head);  
12:          count[i][col-1-j] = grid[i][col-1-j] != '0' ? 0 : (count[i][col-1-j] + tail);  
13:          head = grid[i][j] == 'W' ? 0 : (head + (grid[i][j] == 'E' ? 1 : 0));  
14:          tail = grid[i][col-1-j] == 'W' ? 0 : (tail + (grid[i][col-1-j] == 'E' ? 1 : 0));  
15:        }  
16:      }  
17:      for (j = 0; j < col; j++) {  
18:        for (i = head = tail = 0; i < row; i++) {  
19:          count[i][j] = grid[i][j] != '0' ? 0 : (count[i][j] + head);  
20:          count[row-1-i][j] = grid[row-1-i][j] != '0' ? 0 : (count[row-1-i][j] + tail);  
21:          head = grid[i][j] == 'W' ? 0 : (head + (grid[i][j] == 'E' ? 1 : 0));  
22:          tail = grid[row-1-i][j] == 'W' ? 0 : (tail + (grid[row-1-i][j] == 'E' ? 1 : 0));  
23:        }  
24:      }  
25:      int res = 0;  
26:      for (i = 0; i < row; i++) {  
27:        for (j = 0; j < col; j++) {  
28:          res = max(res, count[i][j]);  
29:        }  
30:      }  
31:      return res;  
32:    }  
33:  };