Number of Islands

Medium

Given an m x n grid of '1' (land) and '0' (water), return the number of islands. An island is surrounded by water and formed by connecting adjacent land cells horizontally or vertically.

Example 1

Input:  grid = ["11110","11010","11000","00000"]
Output: 1

Example 2

Input:  grid = ["11000","11000","00100","00011"]
Output: 3

Constraints

• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.