Posts tagged as “easy”

花花酱 LeetCode 1678. Goal Parser Interpretation

By zxi on December 5, 2020

You own a Goal Parser that can interpret a string command. The command consists of an alphabet of "G", "()" and/or "(al)" in some order. The Goal Parser will interpret "G" as the string "G", "()" as the string "o", and "(al)" as the string "al". The interpreted strings are then concatenated in the original order.

Given the string command, return the Goal Parser‘s interpretation of command.

Example 1:

Input: command = "G()(al)"
Output: "Goal"
Explanation: The Goal Parser interprets the command as follows:
G -> G
() -> o
(al) -> al
The final concatenated result is "Goal".

Example 2:

Input: command = "G()()()()(al)"
Output: "Gooooal"

Example 3:

Input: command = "(al)G(al)()()G"
Output: "alGalooG"

Constraints:

1 <= command.length <= 100
command consists of "G", "()", and/or "(al)" in some order.

Solution: String

If we encounter ‘(‘ check the next character to determine whether it’s ‘()’ or ‘(al’)

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

string interpret(string command) {

string ans;

for (int i = 0; i < command.size(); ++i) {

if (command[i] == 'G') ans += "G";

else if (command[i] == '(') {

if (command[i + 1] == ')') ans += "o";

else ans += "al";

}

return ans;

}

};

Python3

class Solution:

def interpret(self, command: str) -> str:

ans = []

for i, c in enumerate(command):

if c == 'G': ans.append('G')

elif c == '(':

ans.append('o' if command[i + 1] == ')' else 'al')

return ''.join(ans)

花花酱 LeetCode 1672. Richest Customer Wealth

By zxi on November 29, 2020

You are given an m x n integer grid accounts where accounts[i][j] is the amount of money the i^th customer has in the j^th bank. Return the wealth that the richest customer has.

A customer’s wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.

Example 1:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.

Example 2:

Input: accounts = [[1,5],[7,3],[3,5]]
Output: 10
Explanation: 
1st customer has wealth = 6
2nd customer has wealth = 10 
3rd customer has wealth = 8
The 2nd customer is the richest with a wealth of 10.

Example 3:

Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Output: 17

Constraints:

m == accounts.length
n == accounts[i].length
1 <= m, n <= 50
1 <= accounts[i][j] <= 100

Solution: Sum each row up

Time complexity: O(mn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maximumWealth(vector<vector<int>>& accounts) {

int ans = 0;

for (const vector<int>& row : accounts)

ans = max(ans, accumulate(begin(row), end(row), 0));

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def maximumWealth(self, accounts: List[List[int]]) -> int:

return max(sum(account) for account in accounts)

花花酱 LeetCode 1668. Maximum Repeating Substring

By zxi on November 28, 2020

For a string sequence, a string word is k-repeating if word concatenated k times is a substring of sequence. The word‘s maximum k-repeating value is the highest value k where word is k-repeating in sequence. If word is not a substring of sequence, word‘s maximum k-repeating value is 0.

Given strings sequence and word, return the maximum k-repeating value of word in sequence.

Example 1:

Input: sequence = "ababc", word = "ab"
Output: 2
Explanation: "abab" is a substring in "ababc".

Example 2:

Input: sequence = "ababc", word = "ba"
Output: 1
Explanation: "ba" is a substring in "ababc". "baba" is not a substring in "ababc".

Example 3:

Input: sequence = "ababc", word = "ac"
Output: 0
Explanation: "ac" is not a substring in "ababc".

Constraints:

1 <= sequence.length <= 100
1 <= word.length <= 100
sequence and word contains only lowercase English letters.

Solution: Brute Force

Time complexity: O(n^2)
Space complexity: O(n)

C++

class Solution {

public:

int maxRepeating(string sequence, string word) {

string s(word);

for (int i = 1;;++i) {

if (sequence.find(s) == string::npos) return i - 1;

s += word;

}

return -1;

}

};

花花酱 LeetCode 1662. Check If Two String Arrays are Equivalent

By zxi on November 22, 2020

Given two string arrays word1 and word2, returntrue if the two arrays represent the same string, and false otherwise.

A string is represented by an array if the array elements concatenated in order forms the string.

Example 1:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true

Constraints:

1 <= word1.length, word2.length <= 10³
1 <= word1[i].length, word2[i].length <= 10³
1 <= sum(word1[i].length), sum(word2[i].length) <= 10³
word1[i] and word2[i] consist of lowercase letters.

Solution1: Construct the string

Time complexity: O(l1 + l2)
Space complexity: O(l1 + l2)

C++

class Solution {

public:

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {

string s1, s2;

for (const string& w1 : word1) s1 += w1;

for (const string& w2 : word2) s2 += w2;

return s1 == s2;

}

};

Solution 2: Pointers

Time complexity: O(l1 + l2)
Space complexity: O(1)

C++

class Solution {

public:

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {

int i1 = 0, j1 = 0;

int i2 = 0, j2 = 0;

while (i1 < word1.size() || i2 < word2.size()) {

char c1 = i1 < word1.size() ? word1[i1][j1++] : '\0';

char c2 = i2 < word2.size() ? word2[i2][j2++] : '\0';

if (c1 != c2) return false;

if (i1 < word1.size() && j1 == word1[i1].length())

++i1, j1 = 0;

if (i2 < word2.size() && j2 == word2[i2].length())

++i2, j2 = 0;

}

return true;

}

};

花花酱 LeetCode 1656. Design an Ordered Stream

By zxi on November 14, 2020

There are n (id, value) pairs, where id is an integer between 1 and n and value is a string. No two pairs have the same id.

Design a stream that takes the n pairs in an arbitrary order, and returns the values over several calls in increasing order of their ids.

Implement the OrderedStream class:

OrderedStream(int n) Constructs the stream to take n values and sets a current ptr to 1.
String[] insert(int id, String value) Stores the new (id, value) pair in the stream. After storing the pair:
- If the stream has stored a pair with id = ptr, then find the longest contiguous incrementing sequence of ids starting with id = ptr and return a list of the values associated with those ids in order. Then, update ptr to the last id + 1.
- Otherwise, return an empty list.

Example:

Input
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
Output
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
Explanation
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns [].
os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"].
os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns [].
os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].

Solution: Straight Forward

Time complexity: O(n) in total
Space complexity: O(n)

C++

// Author: Huahua

class OrderedStream {

public:

OrderedStream(int n): data_(n + 1) {}

vector<string> insert(int id, string value) {

data_[id] = value;

vector<string> ans;

if (ptr_ == id)

while (ptr_ < data_.size() && !data_[ptr_].empty())

ans.push_back(data_[ptr_++]);

return ans;

}

private:

int ptr_ = 1;

vector<string> data_;

};

Python3

# Author: Huahua

class OrderedStream:

def __init__(self, n: int):

self.data = [None] * (n + 1)

self.ptr = 1

def insert(self, id: int, value: str) -> List[str]:

self.data[id] = value

if id == self.ptr:

while self.ptr < len(self.data) and self.data[self.ptr]:

self.ptr += 1

return self.data[id:self.ptr]

return []