Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 664. Strange Printer

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:

C++

Java

Python3

花花酱 LeetCode 200. Number of Islands

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:

Answer: 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)

Solution

C++

Java

Python

Related Problems

花花酱 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 304. Range Sum Query 2D – Immutable

 

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).

Range Sum Query 2D
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:




 

花花酱 LeetCode 221. Maximal Square

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: