Problem:

There is a strange printer with the following two special requirements:

1. The printer can only print a sequence of the same character each time.
2. At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Example 1:

Example 2:

Hint: Length of the given string will not exceed 100.

Idea:

Dynamic programming

Time Complexity:

O(n^3)

Space Complexity:

O(n^2)

Solution:

Python3

Problem:

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Example 2:

Idea: DFS

Use DFS to find a connected component (an island) and mark all the nodes to 0.

Time complexity: O(mn)

Space complexity: O(mn)

Related Problems

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

https://leetcode.com/problems/range-sum-query-2d-immutable/description/

Problem:

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Note:

1. You may assume that the matrix does not change.
2. There are many calls to sumRegion function.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.
Idea:
Dynamic programming
Time complexity:
O(n^2)
sumRegion: O(1)
Solution:

Problem:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Idea:

Dynamic programming

Solution 0: O(n^5)

Solution 1: O(n^3)

Solution 2: O(n^2)

Solution 1:

Solution 2:

Mission News Theme by Compete Themes.