Posts tagged as “string”

花花酱 LeetCode 2125. Number of Laser Beams in a Bank

By zxi on January 2, 2022

Anti-theft security devices are activated inside a bank. You are given a 0-indexed binary string array bank representing the floor plan of the bank, which is an m x n 2D matrix. bank[i] represents the i^th row, consisting of '0's and '1's. '0' means the cell is empty, while'1' means the cell has a security device.

There is one laser beam between any two security devices if both conditions are met:

The two devices are located on two different rows: r₁ and r₂, where r₁ < r₂.
For each row i where r₁ < i < r₂, there are no security devices in the i^th row.

Laser beams are independent, i.e., one beam does not interfere nor join with another.

Return the total number of laser beams in the bank.

Example 1:

Input: bank = ["011001","000000","010100","001000"]
Output: 8
Explanation: Between each of the following device pairs, there is one beam. In total, there are 8 beams:
 * bank[0][1] -- bank[2][1]
 * bank[0][1] -- bank[2][3]
 * bank[0][2] -- bank[2][1]
 * bank[0][2] -- bank[2][3]
 * bank[0][5] -- bank[2][1]
 * bank[0][5] -- bank[2][3]
 * bank[2][1] -- bank[3][2]
 * bank[2][3] -- bank[3][2]
Note that there is no beam between any device on the 0^th row with any on the 3^rd row.
This is because the 2^nd row contains security devices, which breaks the second condition.

Example 2:

Input: bank = ["000","111","000"]
Output: 0
Explanation: There does not exist two devices located on two different rows.

Constraints:

m == bank.length
n == bank[i].length
1 <= m, n <= 500
bank[i][j] is either '0' or '1'.

Solution: Rule of product

Just need to remember the # of devices of prev non-empty row.
# of beams between two non-empty row equals to row[i] * row[j]
ans += prev * curr

Time complexity: O(m*n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int numberOfBeams(vector<string>& bank) {

int ans = 0;

int prev = 0;

for (const string& row : bank)

if (int curr = count(begin(row), end(row), '1')) {

ans += prev * curr;

prev = curr;

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def numberOfBeams(self, bank: List[str]) -> int:

ans = prev = 0

for row in bank:

if curr := row.count('1'):

ans += prev * curr

prev = curr

return ans

花花酱 LeetCode 2124. Check if All A’s Appears Before All B’s

By zxi on January 2, 2022

Given a string s consisting of only the characters 'a' and 'b', return true if every 'a' appears before every 'b' in the string. Otherwise, return false.

Example 1:

Input: s = "aaabbb"
Output: true
Explanation:
The 'a's are at indices 0, 1, and 2, while the 'b's are at indices 3, 4, and 5.
Hence, every 'a' appears before every 'b' and we return true.

Example 2:

Input: s = "abab"
Output: false
Explanation:
There is an 'a' at index 2 and a 'b' at index 1.
Hence, not every 'a' appears before every 'b' and we return false.

Example 3:

Input: s = "bbb"
Output: true
Explanation:
There are no 'a's, hence, every 'a' appears before every 'b' and we return true.

Constraints:

`1 <= s.length <= 100`

`s[i]` is either `'a'` or `'b'`.

Solution: Count bs

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

C++

// Author: Huahua

class Solution {

public:

bool checkString(string s) {

int b = 0;

for (char ch : s) {

b += ch == 'b';

if (ch == 'a' && b) return false;

}

return true;

}

};

花花酱 LeetCode 1980. Find Unique Binary String

By zxi on December 31, 2021

Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.

Example 1:

Input: nums = ["01","10"]
Output: "11"
Explanation: "11" does not appear in nums. "00" would also be correct.

Example 2:

Input: nums = ["00","01"]
Output: "11"
Explanation: "11" does not appear in nums. "10" would also be correct.

Example 3:

Input: nums = ["111","011","001"]
Output: "101"
Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.

Constraints:

n == nums.length
1 <= n <= 16
nums[i].length == n
nums[i] is either '0' or '1'.
All the strings of nums are unique.

Solution 1: Hashtable

We can use bitset to convert between integer and binary string.

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

C++

// Author: Huahua

class Solution {

public:

string findDifferentBinaryString(vector<string>& nums) {

const int n = nums.size();

unordered_set<int> seen(1 << n);

for (const string& num : nums)

seen.insert(bitset<16>(num).to_ulong());

for (int i = 0; i < 1 << n; ++i)

if (!seen.count(i)) return bitset<16>(i).to_string().substr(16 - n);

return "";

}

};

Solution 2: One bit a time

Let ans[i] = ‘1’ – nums[i][i], s.t. ans is at least one bit different from any strings.

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

C++

// Author: Huahua

class Solution {

public:

string findDifferentBinaryString(vector<string>& nums) {

const int n = nums.size();

string ans(n, '0');

for (int i = 0; i < n; ++i)

ans[i] = '1' - nums[i][i] + '0';

return ans;

}

};

花花酱 LeetCode 1967. Number of Strings That Appear as Substrings in Word

By zxi on December 31, 2021

Given an array of strings patterns and a string word, return the number of strings in patterns that exist as a substring in word.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: patterns = ["a","abc","bc","d"], word = "abc"
Output: 3
Explanation:
- "a" appears as a substring in "abc".
- "abc" appears as a substring in "abc".
- "bc" appears as a substring in "abc".
- "d" does not appear as a substring in "abc".
3 of the strings in patterns appear as a substring in word.

Example 2:

Input: patterns = ["a","b","c"], word = "aaaaabbbbb"
Output: 2
Explanation:
- "a" appears as a substring in "aaaaabbbbb".
- "b" appears as a substring in "aaaaabbbbb".
- "c" does not appear as a substring in "aaaaabbbbb".
2 of the strings in patterns appear as a substring in word.

Example 3:

Input: patterns = ["a","a","a"], word = "ab"
Output: 3
Explanation: Each of the patterns appears as a substring in word "ab".

Constraints:

1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] and word consist of lowercase English letters.

Solution: Brute Force

We can use count_if for 1-liner.

Time complexity: O(m*n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int numOfStrings(vector<string>& patterns, string word) {

return count_if(begin(patterns), end(patterns), [&](string& p) {

return word.find(p) != string::npos;

});

}

};

花花酱 LeetCode 1961. Check If String Is a Prefix of Array

By zxi on December 31, 2021

Given a string s and an array of strings words, determine whether s is a prefix string of words.

A string s is a prefix string of words if s can be made by concatenating the first k strings in words for some positive k no larger than words.length.

Return true if s is a prefix string of words, or false otherwise.

Example 1:

Input: s = "iloveleetcode", words = ["i","love","leetcode","apples"]
Output: true
Explanation:
s can be made by concatenating "i", "love", and "leetcode" together.

Example 2:

Input: s = "iloveleetcode", words = ["apples","i","love","leetcode"]
Output: false
Explanation:
It is impossible to make s using a prefix of arr.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 20
1 <= s.length <= 1000
words[i] and s consist of only lowercase English letters.

Solution: Concat and test

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

C++

// Author: Huahua

class Solution {

public:

bool isPrefixString(string s, vector<string>& words) {

string t;

for (const string& w : words) {

t += w;

if (t.length() >= s.length()) break;

}

return t == s;

}

};

Posts tagged as “string”

花花酱 LeetCode 2125. Number of Laser Beams in a Bank

Solution: Rule of product

C++

Python3

花花酱 LeetCode 2124. Check if All A’s Appears Before All B’s

1 <= s.length <= 100

s[i] is either 'a' or 'b'.Solution: Count bs

C++

花花酱 LeetCode 1980. Find Unique Binary String

Solution 1: Hashtable

C++

Solution 2: One bit a time

C++

花花酱 LeetCode 1967. Number of Strings That Appear as Substrings in Word

Solution: Brute Force

C++

花花酱 LeetCode 1961. Check If String Is a Prefix of Array

Solution: Concat and test

C++

`1 <= s.length <= 100`

`s[i]` is either `'a'` or `'b'`.

Solution: Count bs