Press "Enter" to skip to content

Posts tagged as “counting”

花花酱 LeetCode 91. Decode Ways

题目大意:

给你一个加密的数字字符串,问你一共有多少种不同的解密方式。

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1

‘B’ -> 2

‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

 



Idea:

Dynamic Programming

Solution:

C++

Time complexity: O(n^2)

Space complexity: O(n^2)

 

C++

Time complexity: O(n)

Space complexity: O(n)

 

 

 

C++

Time complexity: O(n)

Space complexity: O(1)

 

Related Problems:

花花酱 LeetCode 678. Valid Parenthesis String

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:

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

Example 1:

Example 2:

Example 3:

Note:

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



Idea:

Dynamic Programming / Counting

Solution 1:

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

 

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

 

C++ / Counting O(n)

 

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

 

花花酱 LeetCode 409. Longest Palindrome

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:

Idea:

Greedy + Counting



Solution:

C++

 

Java

 

 

Python

 

花花酱 LeetCode 673. Number of Longest Increasing Subsequence

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:

Example 2:

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:

Solution2:

Related Problems:

花花酱 Leetcode 419. Battleships in a Board