counting Archives - Page 7 of 7 - Huahua's Tech Road

花花酱 LeetCode 678. Valid Parenthesis String

By zxi on September 30, 2017

Problem:

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
An empty string is also valid.

Example 1:

1 2	Input: "()" Output: True

Example 2:

1 2	Input: "(*)" Output: True

Example 3:

1 2	Input: "(*))" Output: True

Note:

The string size will be in the range [1, 100].

Idea:

Dynamic Programming / Counting

Solution 1:

C++ / DP / Top-down O(n^3)

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

bool checkValidString(const string& s) {

int l = s.length();

m_ = vector<vector<int>>(l, vector<int>(l, -1));

return isValid(s, 0, l - 1);

}

private:

vector<vector<int>> m_;

bool isValid(const string& s, int i, int j) {

if (i > j) return true;

if (m_[i][j] >= 0) return m_[i][j];

if (i == j) return m_[i][j] = (s[i] == '*');

if ((s[i] == '(' || s[i] == '*')

&&(s[j] == ')' || s[j] == '*')

&& isValid(s, i + 1, j - 1))

return m_[i][j] = 1;

for (int p = i; p < j; ++p)

if (isValid(s, i, p) && isValid(s, p + 1, j))

return m_[i][j] = 1;

return m_[i][j] = 0;

}

};

C++ / DP/ Bottom-up O(n^3)

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

bool checkValidString(const string& s) {

int l = s.length();

if (l == 0) return true;

vector<vector<int>> dp(l, vector<int>(l, 0));

for (int i = 0; i < l; ++i)

if (s[i] == '*') dp[i][i] = 1;

for (int len = 2; len <= l; ++len)

for (int i = 0; i <= l - len; ++i) {

int j = i + len - 1;

// (...), *...), (...*, *...*

if ((s[i] == '(' || s[i] == '*')

&&(s[j] == ')' || s[j] == '*'))

if (len == 2 || dp[i + 1][j - 1]) {

dp[i][j] = 1;

continue;

}

for (int k = i; k < j; ++k)

if (dp[i][k] && dp[k + 1][j]) {

dp[i][j] = 1;

break;

}

return dp[0][l - 1];

}

};

C++ / Counting O(n)

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

bool checkValidString(string s) {

int min_op = 0;

int max_op = 0;

for (char c : s) {

if (c == '(') ++min_op; else --min_op;

if (c != ')') ++max_op; else --max_op;

if (max_op < 0) return false;

min_op = max(0, min_op);

}

return min_op == 0;

}

};

Java / DP / Bottom-up O(n^3)

class Solution {

public boolean checkValidString(String s) {

int l = s.length();

if (l == 0) return true;

boolean[][] dp = new boolean[l][l];

char[] ss = s.toCharArray();

for (int i = 0; i < l; ++i)

if (ss[i] == '*') dp[i][i] = true;

for (int len = 2; len <= l; ++len)

for (int i = 0; i + len <= l; ++i) {

int j = i + len - 1;

if ((ss[i] == '*' || ss[i] == '(')

&&(ss[j] == '*' || ss[j] == ')')) {

if (len == 2 || dp[i + 1][j - 1]) {

dp[i][j] = true;

continue;

}

for (int k = i; k < j; ++k)

if (dp[i][k] && dp[k + 1][j]) {

dp[i][j] = true;

break;

}

return dp[0][l - 1];

}

花花酱 LeetCode 409. Longest Palindrome

By zxi on September 19, 2017

https://leetcode.com/problems/longest-palindrome/description/

Problem:

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:

"abccccdd"

Output:

Explanation:

One longest palindrome that can be built is "dccaccd", whose length is 7.

Idea:

Greedy + Counting

Solution:

C++

// Author: Huahua

// Time complexity: O(n)

// Space complexity: O(128) = O(1)

// Running time: 3 ms 9/2017

class Solution {

public:

int longestPalindrome(const string& s) {

vector<int> freqs(128, 0);

for (const char c : s)

++freqs[c];

int ans = 0;

int odd = 0;

for (const int freq : freqs) {

// same as: ans += freq % 2 == 0 ? freq : freq - 1;

// same as: ans += freq / 2 * 2;

// same as: ans += ((freq >> 1) << 1);

// same as: ans += freq & (INT_MAX - 1);

ans += freq & (~1); // clear the last bit

odd |= freq & 1;

}

ans += odd;

return ans;

}

};

Java

// Author: Huahua

// Running time: 11 ms

class Solution {

public int longestPalindrome(String s) {

int[] freqs = new int[128];

for (int i = 0; i < s.length(); ++i)

++freqs[s.charAt(i)];

int ans = 0;

int odd = 0;

for (int freq: freqs) {

ans += freq & (~1);

odd |= freq & 1;

}

return ans + odd;

}

Python

"""

Author: Huahua

Running time: 39 ms

"""

class Solution(object):

def longestPalindrome(self, s):

"""

:type s: str

:rtype: int

"""

freqs = [0] * 128

for c in s:

freqs[ord(c)] += 1

ans, odd = 0, 0

for freq in freqs:

ans += freq & (~1)

odd |= freq & 1

return ans + odd

花花酱 LeetCode 673. Number of Longest Increasing Subsequence

By zxi on September 15, 2017

https://leetcode.com/problems/number-of-longest-increasing-subsequence

Problem:

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]

Output: 2

Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]

Output: 5

Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Idea:

Dynamic programming

Solution1:

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

int findNumberOfLIS(vector<int>& nums) {

int n = nums.size();

if (n == 0) return 0;

c_ = vector<int>(n, 0);

l_ = vector<int>(n, 0);

// Find the length LIS.

int max_len = 0;

for (int i = 0; i < n; ++i)

max_len = max(max_len, len(nums, i));

// Checking all endings.

int ans = 0;

for (int i = 0; i < n; ++i)

if (len(nums, i) == max_len)

ans += count(nums, i);

return ans;

}

private:

vector<int> c_; // c[i]: number of LIS ends with nums[i] / NLIS'

vector<int> l_; // l[i]: lengeh of LIS ends with nums[i] / LIS'

// Number of LIS ends with nums[n]

int count(const vector<int>& nums, int n) {

if (n == 0) return 1;

if (c_[n] > 0) return c_[n];

int total_count = 0;

int l = len(nums, n);

for (int i = 0; i < n; ++i)

if (nums[n] > nums[i] && len(nums, i) == l-1)

total_count += count(nums, i);

if (total_count == 0)

total_count = 1;

return c_[n] = total_count;

}

// Length of LIS ends with nums[n]

int len(const vector<int>& nums, int n) {

if (n == 0) return 1;

if (l_[n] > 0) return l_[n];

int max_len = 1;

// Check every subarray

for (int i = 0; i < n; ++i)

if (nums[n] > nums[i])

max_len = max(max_len, len(nums, i) + 1);

return l_[n] = max_len;

}

};

Solution2:

// Author: Huahua

// Running time: 33 ms

class Solution {

public:

int findNumberOfLIS(vector<int>& nums) {

int n = nums.size();

if (n == 0) return 0;

vector<int> c(n, 1);

vector<int> l(n, 1);

for (int i = 1; i < n; ++i)

for(int j = 0; j < i; ++j)

if (nums[i] > nums[j]) {

if (l[j] + 1 > l[i]) {

l[i] = l[j] + 1;

c[i] = c[j];

} else if (l[j] + 1 == l[i]) {

c[i] += c[j];

}

int max_len = *max_element(l.begin(), l.end());

int ans = 0;

for (int i = 0; i < n; ++i)

if (l[i] == max_len)

ans += c[i];

return ans;

}

};

Related Problems:

花花酱 Leetcode 419. Battleships in a Board

By zxi on March 12, 2017

class Solution {

public:

int countBattleships(vector<vector<char>>& board) {

int count = 0;

for(int i=0;i<board.size();++i)

for(int j=0;j<board[i].size();++j) {

if(board[i][j] == 'X'

&& (i==0 || board[i-1][j] == '.')

&& (j==0 || board[i][j-1] == '.')) ++count;

}

return count;

}

};

Posts tagged as “counting”

花花酱 LeetCode 678. Valid Parenthesis String

花花酱 LeetCode 409. Longest Palindrome

花花酱 LeetCode 673. Number of Longest Increasing Subsequence

花花酱 Leetcode 419. Battleships in a Board