Fork me on GitHub
image frame

Yangyang

Think. Learn. Create
Try to update hard.

Leetcode Study Day 19

Leetcode

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Example 1:

Input: s = "egg", t = "add"
Output: true
Example 2:

Input: s = "foo", t = "bar"
Output: false
Example 3:

Input: s = "paper", t = "title"
Output: true
 

Constraints:

1 <= s.length <= 5 * 104
t.length == s.length
s and t consist of any valid ascii character.

My solution

My solution is using unordered_map to store the mapping between characters in s and t. We loop through the string s and check if the character is in the unordered_map. If it is, we check if the character in t is the same as the character in unordered_map. If it is not, we return false. If it is, we continue to check the next character in s. After the iteration, we can make sure that all the characters in s can be mapped to t.

Then we clear the unordered_map and do the same thing for t and s. If all the characters in t can be mapped to s, we return true. Otherwise, we return false.

An example if we only check s and t once:

1
2
s = "badc"
t = "baba"

In this case, if we only check whether the characters in s can be mapped to t, we will get the result true. However, the character b in the string t can be mapped to a and d in the string s. Therefore, we need to check whether the characters in t can be mapped to s as well.

Full code

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
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) return false;
        unordered_map<char, char> wordMatch;
        for (int i = 0; i < s.size(); i ++){
            auto ifMatch = wordMatch.find(s[i]);
            // don't find the element in the map
            if (ifMatch == wordMatch.end())
                wordMatch[s[i]] = t[i];
            // find the element in the map
            if (ifMatch != wordMatch.end()){
                if (wordMatch[s[i]] != t[i])
                    return false;
            }
        }
        wordMatch.clear();
        for (int i = 0; i < t.size(); i ++){
            auto ifMatch = wordMatch.find(t[i]);
            // don't find the element in the map
            if (ifMatch == wordMatch.end())
                wordMatch[t[i]] = s[i];
            // find the element in the map
            if (ifMatch != wordMatch.end()){
                if (wordMatch[t[i]] != s[i])
                    return false;
            }
        }        
        return true;
    }
};

Leetcode Study Day 19

Leetcode

Ransom Note

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false
Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true
 

Constraints:

1 <= ransomNote.length, magazine.length <= 105
ransomNote and magazine consist of lowercase English letters.

My solution

My solution is creating an unordered_map to store each character in the string magazine. We count how many times each character appear.

Then we loop the string ransomNote and check if the character is in the unordered_map. If it is, we decrease the count by 1. If it is not, we return false.
If the count for this character is already equal to 0, which means this character has already appeared once, than we return false.

One knowledge need to methion is that in C++ unordered_map, if the key is not in the map, the find() function will return the end() iterator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> wordCount;
        for (int i = 0; i < magazine.size(); i++)
            wordCount[magazine[i]]++;
        for (int i = 0; i < ransomNote.size(); i++){
            auto findResult = wordCount.find(ransomNote[i]);
            if (findResult != wordCount.end()){
                if (wordCount[ransomNote[i]] == 0){
                    return false;
                }
                wordCount[ransomNote[i]] --;
            }
            else
                return false;
        }
        return true;
    }
};

Leetcode Study Day 18

Leetcode

Game of Life

According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population.
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:


Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
Example 2:


Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]
 

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] is 0 or 1.

My solution

My solution is intuitive. I create a new matrix to store the next state of the board. Then I iterate through the board and check the number of live neighbours. Then I apply the rules to the new matrix. Finally, I copy the new matrix to the board.

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
59
class Solution {
public:

    void gameOfLife(vector<vector<int>>& board) {
        vector<vector<int>> answer(board.size(), vector<int>(board[0].size(), 0));
        for (int i = 0; i < board.size(); i ++){
            for (int j = 0; j < board[0].size(); j++){
                int count = 0;
                // check neighbours
                // up-left
                if (j!= 0 && i != 0){
                    int up_left = board[i-1][j-1];
                    count += up_left;
                }
                // up 
                if (i != 0){
                    int up = board[i-1][j];
                    count += up;
                }
                // up-right
                if (j != board[0].size()-1 && i != 0)
                    {int up_right = board[i-1][j+1];
                    count += up_right;}
                // left
                if (j != 0)
                    {int left = board[i][j-1];
                    count += left;}
                // right
                if (j != board[0].size() -1)
                    {int right = board[i][j+1];
                    count += right;}
                // down-left
                if (j != 0 && i!= board.size() -1)
                    {int down_left = board[i+1][j-1];
                    count += down_left;}
                // down
                if (i != board.size() - 1)
                    {int down = board[i+1][j];
                    count += down;}
                // down-right
                if (i != board.size() - 1 && j != board[0].size()-1)
                    {int down_right = board[i+1][j+1];
                    count += down_right;}
                if (board[i][j] == 1 && count < 2){
                    answer[i][j] = 0;
                }
                else if (board[i][j] == 1 && count > 3){
                    answer[i][j] = 0;
                }
                else if (board[i][j] == 0 && count == 3){
                    answer[i][j] = 1;
                }
                else
                    answer[i][j] = board[i][j];
            }
        }
        board = answer;
    }
};

O(1) space, O(mn) time

I found a solution using O(1) space and O(mn) time to solve this question. The reason that he solved it in O(1) space is because he used the second bit to store the next state of the cell.

Let’s break down the code, line by line:

1
int m=board.size(), n=m?board[0].size():0;

We define two integer variables m and n:

  • m stores the number of rows of the board.
  • n stores the number of columns of the board if m is not zero. If m is zero (i.e., board is empty), n is set to zero.
1
2
for(int i=0; i<m; i++){
    for(int j=0; j<n; j++){

These nested loops iterate over each cell in the board.

1
int count=0;

This initializes a counter to count the number of live neighbors for the current cell (i, j).

1
2
for(int ss=max(i-1, 0); ss<min(i+2, m); ss++){
    for(int tt=max(j-1, 0); tt<min(j+2, n); tt++){

These nested loops iterate over the neighbors of the current cell (i, j). They ensure that the loops do not go out of bounds by using the max and min functions.

1
count+=board[ss][tt]&1;

Here, the code checks the least significant bit of the neighboring cell (ss, tt) to see if it’s alive (1) or dead (0). The operation & 1 when applied to an integer effectively isolates the least significant bit (LSB) of its binary representation. The result is added to the count, which accumulates the number of live neighbors.

1
2
}
count-=board[i][j];

After counting all the live neighbors, we subtract the state of the current cell (i, j) from the count since we included it in our previous loop.

1
2
if(count==3 || (board[i][j]&&count==2))
    board[i][j]|=2;

Here, we’re applying the rules of Conway’s Game of Life:

  • If a cell has exactly 3 live neighbors, it becomes alive (or stays alive).
  • If a live cell has exactly 2 live neighbors, it stays alive.

The board[i][j] |= 2; operation sets the second least significant bit of the current cell to 1, indicating that the cell will be alive in the next state.

These close the nested loops iterating over each cell in the board.

1
2
3
for(int i=0; i<m; i++)
    for(int j=0; j<n; j++)
        board[i][j]>>=1;

These nested loops go over each cell in the board again. For each cell, it right shifts its bits by one position. This is done to update the board to its next state by making the second least significant bit (which represents the next state) the current state.

The cleverness of this implementation lies in its use of bitwise operations to store both the current state and the next state of each cell in the same integer. This way, the algorithm can compute the next state of the board in-place without needing additional memory for a temporary board.

Leetcode Study Day 18

Leetcode

Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.

You must do it in place.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:


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


Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
 

Constraints:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

Solution

The solution is to move the elements with 0 value to the boundary of the martix, which is the first row and the first column specifically, then we can use the first row and the first column to mark the rows and columns that need to be set to 0.

Let’s breakdown the solution step by step:

  1. Check if the first row and the first column contains 0. If so, we set two boolean variables isZeroCol and isZeroCol to true.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int length = matrix[0].size();
    int height = matrix.size();
    bool isZeroCol = false;
    bool isZeroRow = false;
    // Check the first row
    for (int i = 0; i < length; i++){
        if(matrix[0][i] == 0){
            isZeroRow = true;
            break;
        }
    }

    // Check the first column
    for (int i = 0; i < height; i++){
        if(matrix[i][0] == 0){
            isZeroCol = true;
            break;
        }
    }
  2. Iterate through the matrix, if the element is 0, set the first element of the row and the column to 0.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // Check columns and rows except the first one
    for (int i = 1; i < height; i++){
        for (int j = 1; j < length; j++){
            if (matrix[i][j]==0){
                matrix[0][j] = 0;
                matrix[i][0] = 0;
            }
        }
    }
  3. We check if there is any element in first row and first column is 0, if so, we set the whole row and column to 0.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // Set columns and rows except the first one to 0
    for (int i = 1; i < height; i++){
        for (int j = 1; j < length; j++){
            if (matrix[0][j]==0)
                matrix[i][j] = 0;
            if (matrix[i][0]==0)
                matrix[i][j] = 0;
        }
    }
  4. Finally, we set the first row and the first column to 0 if our boolean flag is true.
1
2
3
4
5
6
7
8
9
10
11
// Now set the first column if there exists 0 in first column
if (isZeroCol){
    for (int i = 0; i < height; i++)
        matrix[i][0] = 0;
}

// Now set the first row if there exists 0 in first row
if (isZeroRow){
    for (int i = 0; i < length; i++)
        matrix[0][i] = 0;
}

Full code

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
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int length = matrix[0].size();
        int height = matrix.size();
        bool isZeroCol = false;
        bool isZeroRow = false;
        // Check the first row
        for (int i = 0; i < length; i++){
            if(matrix[0][i] == 0){
                isZeroRow = true;
                break;
            }
        }

        // Check the first column
        for (int i = 0; i < height; i++){
            if(matrix[i][0] == 0){
                isZeroCol = true;
                break;
            }
        }

        // Check columns and rows except the first one
        for (int i = 1; i < height; i++){
            for (int j = 1; j < length; j++){
                if (matrix[i][j]==0){
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        // Set columns and rows except the first one to 0
        for (int i = 1; i < height; i++){
            for (int j = 1; j < length; j++){
                if (matrix[0][j]==0)
                    matrix[i][j] = 0;
                if (matrix[i][0]==0)
                    matrix[i][j] = 0;
            }
        }

        // Now set the first column if there exists 0 in first column
        if (isZeroCol){
            for (int i = 0; i < height; i++)
                matrix[i][0] = 0;
        }

        // Now set the first row if there exists 0 in first row
        if (isZeroRow){
            for (int i = 0; i < length; i++)
                matrix[0][i] = 0;
        }
    }
};

Leetcode Study Day 17

Leetcode

Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

1
2
3
4
5
6
7
8
9
10
11
Example 1:


Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:


Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Solution

Rotating a 2D matrix (or image) by 90 degrees in-place can be broken down into two steps:

  1. Transpose the Matrix: This means converting all the rows of the matrix into columns.

    1
    2
    3
    a b

    c d

    becomes

    1
    2
    3
    a c

    b d

  2. Reverse the Columns: After transposition, the columns are reversed (or you can think of it as reversing each row).

    Taking the transposed matrix from the example above:

    1
    2
    3
    a c

    b d

    becomes

    1
    2
    3
    c a

    d b

    which is the original matrix rotated 90 degrees clockwise.

Here’s a step-by-step breakdown:

  1. Transpose the Matrix:
    • Loop through the matrix.
    • For each element at position ((i, j)), swap it with the element at position ((j, i)). Note: We only need to swap the elements once, so ensure that we are not swapping them back in a later iteration.
1
2
3
4
5
6
7
8
9
10
int length = matrix.size();
int start = 0;
for (int i = 0; i < length; i++){
    for (int j = start; j < length; j++){
        int cache = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = cache;
    }
    start ++;
}
  1. Reverse the Columns:
    • Loop through the matrix.
    • For each row, reverse the elements in the row. This can be achieved by swapping the first element with the last, the second with the second last, and so on.
1
2
3
4
5
6
7
for (int i = 0; i < length  ; i ++){
    for (int j = 0; j < length/2; j++){
        int cache = matrix[i][length-1-j];
        matrix[i][length-1-j] = matrix[i][j];
        matrix[i][j] = cache;
    }
}

Full code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int length = matrix.size();
        int start = 0;
        for (int i = 0; i < length; i++){
            for (int j = start; j < length; j++){
                int cache = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = cache;
            }
            start ++;
        }
        for (int i = 0; i < length  ; i ++){
            for (int j = 0; j < length/2; j++){
                int cache = matrix[i][length-1-j];
                matrix[i][length-1-j] = matrix[i][j];
                matrix[i][j] = cache;
            }
        }

    }
};

Leetcode Study Day 17

Leetcode

Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:


Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:


Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
 

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

Solution

The solution is actually easy to understand. Firstly, we found the width and the height of the matrix:

1
2
3
int width = matrix[0].size();
int height = matrix.size();
int count = width * height;

Then we initialise four pointers for this matrix, which is up, right, down and left. We also initialise a vector to store the answer.

1
2
int left = 0, right = width - 1, up = 0, down = height - 1;
vector<int> answer;

Then we use a while loop to iterate through the matrix. We use four for loops to iterate through the matrix. The first for loop is to iterate through the top row, the second for loop is to iterate through the right column, the third for loop is to iterate through the bottom row and the last for loop is to iterate through the left column. After each for loop, we need to check if the size of the answer array is greater than the total size, if it is, we break the while loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while (answer.size() < count){
        for (int i = left; i <= right && answer.size() < count ; i++){
            answer.push_back(matrix[up][i]);
        }
        for (int i = up + 1; i <= down - 1 && answer.size() < count; i++){
            answer.push_back(matrix[i][right]);
        }
        for (int i = right; i >= left && answer.size() < count; i--){
            answer.push_back(matrix[down][i]);
        }
        for (int i = down - 1; i >= up + 1 && answer.size() < count; i--){
            answer.push_back(matrix[i][left]);
        }            
        left ++;
        right --;
        up ++;
        down --;
    }

Finally, we return our answer array.

Full code

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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int width = matrix[0].size();
        int height = matrix.size();
        int count = width * height;
        int left = 0, right = width - 1, up = 0, down = height - 1;
        vector<int> answer;
        while (answer.size() < count){
            for (int i = left; i <= right && answer.size() < count ; i++){
                answer.push_back(matrix[up][i]);
            }
            for (int i = up + 1; i <= down - 1 && answer.size() < count; i++){
                answer.push_back(matrix[i][right]);
            }
            for (int i = right; i >= left && answer.size() < count; i--){
                answer.push_back(matrix[down][i]);
            }
            for (int i = down - 1; i >= up + 1 && answer.size() < count; i--){
                answer.push_back(matrix[i][left]);
            }            
            left ++;
            right --;
            up ++;
            down --;
        }
        return answer;
    }
};

Leetcode Study Day 16

Leetcode

Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

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
Example 1:


Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
 

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.

Solution

This solution is found in the Leetcode discussion board. His idea is to iterate all the elements in the board, and insert this element’s horizontal, vertical and grid information into a set. If the set already contains this element, we return false. Otherwise, we continue the iteration. If the iteration is finished, we return true.

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
class Solution {
public:

bool isValidSudoku(vector<vector<char>>& board) {
    set<string> seen;
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            char number = board[i][j];
            if (number != '.') {
                // Construct the unique strings for row, column, and block checks
                // We use std::string(1, number) to create a single-character string from the char number.
                string rowStr = string(1, number) + " in row " + to_string(i);
                string colStr = string(1, number) + " in column " + to_string(j);
                string blockStr = string(1, number) + " in block " + to_string(i / 3) + "-" + to_string(j / 3);
                
                // Check if any of the strings already exist in the set
                if (!seen.insert(rowStr).second || 
                    !seen.insert(colStr).second || 
                    !seen.insert(blockStr).second)
                    return false;
            }
        }
    }
    return true;
}
};

Leetcode Study Day 16

Leetcode

Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window
substring
of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.

The testcases will be generated such that the answer is unique.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.
 

Constraints:

m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase and lowercase English letters.

My solution

I write specific comments in my code

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
class Solution {
public:
    string minWindow(string s, string t) {
        // A map to store chars with their appears number
        unordered_map <char, int> charCount;
        for (int i = 0; i < t.size(); i++)
            charCount[t[i]] ++;
        int left = 0, right = 0, counter = t.size(), minStart = 0, minLen = INT_MAX;
        while (right < s.size()){
            // if the character in s is in t, we decrease the counter
            if (charCount[s[right]] > 0)
                counter --;
            // Then we decrease the appears number which is stored in the map
            charCount[s[right]] --;
            // we move the right pointer
            right ++;
            // counter equals to 0 means we find a fixed window
            while (counter == 0){
                // we update the minimum length of the substring, and the minStart
                if (right - left < minLen){
                    minLen = right - left;
                    minStart = left;
                }
                // Try to move window to the right position
                charCount[s[left]]++;
                // If it is greater than 0, means s[left] is in t, we need increase the counter
                if (charCount[s[left]] > 0)
                    counter ++;
                // We move the left pointer
                left ++;
            }
        }
        // return the substring is minLen is not MAX
        if (minLen != INT_MAX)
            return s.substr(minStart, minLen);
        return "";
    }
};

Leetcode Study Day 15

Leetcode

Substring with Concatenation of All Words

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.

For example, if words = [“ab”,”cd”,”ef”], then “abcdef”, “abefcd”, “cdabef”, “cdefab”, “efabcd”, and “efcdab” are all concatenated strings. “acdbef” is not a concatenated substring because it is not the concatenation of any permutation of words.
Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
The output order does not matter. Returning [9,0] is fine too.
Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 in s that is equal to the concatenation of any permutation of words.
We return an empty array.
Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words.
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words.
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.

Solution

The solution is firstly, we store the word in the array words in a unordered_map. For each word, we count the number of times it appears. Then we use the sliding window method to find the substring. We use a method checkSubstring to check if the substring of the original input string s is a concatenated substring.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> findSubstring(string s, vector<string>& words) {
        vector <int> answer;
        int singleWordLen = words[0].size();
        int windowSize = words.size() * singleWordLen;
        // creating a map stores words count
        unordered_map <string, int> wordCount;
        for (int i = 0; i < words.size(); i++){
            wordCount[words[i]]++;
        }
        int i = 0;
        while (i + windowSize <= s.size()){
            if (checkSubstring(wordCount, s.substr(i, windowSize), singleWordLen))
                answer.push_back(i);
            i++;
        }
        return answer;
    }

In the function checkSubstring, we iterate the substring, which is passed in the main function and check if the word in the array words is in the substring. If it is, we decrease the count of the word in the map. If the count is equal to -1, which means the word appears more times than it should be, we return false. If the word is not in the map, we return false. If the word is in the map and the count is not equal to -1, we continue to check the next word. If we finish checking all the words in the map, we return true.

It is noticeable that wordCount is passed by value, any changes made to it within the checkSubstring function are local to that function and do not affect the original wordCount map in the findSubstring method. This means that every time checkSubstring is called, it receives a fresh copy of the wordCount map with the original word counts. As a result, there’s no need to reset the map after each call to checkSubstring.

1
2
3
4
5
6
7
8
9
10
11
12
13
bool checkSubstring(unordered_map <string, int> wordCount, string s, int singleWordLen){
    for (int i = 0; i < s.size(); i += singleWordLen){
        string subString = s.substr(i, singleWordLen);
        if (wordCount.find(subString) != wordCount.end()){
            if (--wordCount[subString] == -1)
                return false;
        }
        else
            return false;
    }
    return true;
}

Full code

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
class Solution {
public:
    bool checkSubstring(unordered_map <string, int> wordCount, string s, int singleWordLen){
        for (int i = 0; i < s.size(); i += singleWordLen){
            string subString = s.substr(i, singleWordLen);
            if (wordCount.find(subString) != wordCount.end()){
                if (--wordCount[subString] == -1)
                    return false;
            }
            else
                return false;
        }
        return true;
    }

    vector<int> findSubstring(string s, vector<string>& words) {
        vector <int> answer;
        int singleWordLen = words[0].size();
        int windowSize = words.size() * singleWordLen;
        // creating a map stores words count
        unordered_map <string, int> wordCount;
        for (int i = 0; i < words.size(); i++){
            wordCount[words[i]]++;
        }
        int i = 0;
        while (i + windowSize <= s.size()){
            if (checkSubstring(wordCount, s.substr(i, windowSize), singleWordLen))
                answer.push_back(i);
            i++;
        }
        return answer;
    }
};

Leetcode Study Day 15

Leetcode

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest
substring
without repeating characters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
 

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

My solution

My solution is using the sliding window method. We use two pointers, left and right, to represent the left and right bound of the substring. We move the right pointer to the right until the substring contains a repeating character. Then we move the left pointer to the right and update the maximum length of the substring. We repeat the process until the right pointer reaches the end of the string.

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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0;
        int right = 0;
        int n = s.size();
        int maxCount = INT_MIN;
        string subString = "";

        while (right < n){
            if (subString.find(s[right]) == string::npos){
                subString += s[right];
                right ++;
                maxCount = max(maxCount, int(subString.size()));
            }
            else{
                maxCount = max(maxCount, int(subString.size()));
                left ++;
                right = left;
                subString = "";
            }
            
        }
        return (maxCount == INT_MIN) ? 0 : maxCount;
    }
};

In C++, we can use the find method of the std::string class, if the substring or character I’m looking for is not found, the method will return std::string::npos.

  • Copyrights © 2020-2024 Yangyang Cui

请我喝杯咖啡吧~

支付宝
微信