leetcode/algorithms/ruby/0221-maximal-square.rb at main · remy727/leetcode · GitHub

Name: leetcode/algorithms/ruby/0221-maximal-square.rb at main · remy727/leetcode · GitHub
Rating: 4.9 (9014 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# frozen_string_literal: true

# 221. Maximal Square
# https://leetcode.com/problems/maximal-square
# Medium

=begin
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:
Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:
Input: matrix = [["0"]]
Output: 0

Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] is '0' or '1'.
=end

# @param {Character[][]} matrix
# @return {Integer}
defmaximal_square(matrix)
dp=Array.new(matrix.size + 1){Array.new(matrix[0].size + 1)}
max=0
dp.size.timesdo |i|
dp[0].size.timesdo |j|
ifi == 0 || j == 0 || matrix[i - 1][j - 1] == "0"
dp[i][j]=0
else
dp[i][j]=1 + [dp[i - 1][j - 1],dp[i - 1][j],dp[i][j - 1]].min
end
max=[max,dp[i][j]].max
end
end
max**2
end

# **************** #
# TEST #
# **************** #

require"test/unit"
classTest_maximal_square < Test::Unit::TestCase
deftest_
assert_equal4,maximal_square([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]])
assert_equal1,maximal_square([["0","1"],["1","0"]])
assert_equal0,maximal_square([["0"]])
end
end