Huahua’s Tech Road

花花酱 LeetCode 1003. Check If Word Is Valid After Substitutions

By zxi on March 2, 2019

We are given that the string "abc" is valid.

From any valid string V, we may split V into two pieces X and Y such that X + Y (X concatenated with Y) is equal to V. (X or Y may be empty.) Then, X + "abc" + Y is also valid.

If for example S = "abc", then examples of valid strings are: "abc", "aabcbc", "abcabc", "abcabcababcc". Examples of invalid strings are: "abccba", "ab", "cababc", "bac".

Return true if and only if the given string S is valid.

Example 1:

Input: "aabcbc"
Output: true
Explanation: 
We start with the valid string "abc".
Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".

Example 2:

Input: "abcabcababcc"
Output: true
Explanation: 
"abcabcabc" is valid after consecutive insertings of "abc".
Then we can insert "abc" before the last letter, resulting in "abcabcab" + "abc" + "c" which is "abcabcababcc".

Example 3:

Input: "abccba"
Output: false

Example 4:

Input: "cababc"
Output: false

Note:

1 <= S.length <= 20000
S[i] is 'a', 'b', or 'c'

Solution: Stack

If current char can be appended to the stack do so, if the top of stack is “abc” pop, otherwise push the current char to the stack. Check whether the stack is empty after all chars were processed.

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

C++

// Author: Huahua, running time: 28 ms, 11.9 MB

class Solution {

public:

bool isValid(string S) {

stack<string> st;

for (char ch : S) {

if (st.empty()) {

st.push("");

}

string& s = st.top();

char exp = 'a' + s.length();

if (ch == exp) {

s += ch;

if (s == "abc") st.pop();

} else if (ch != 'a'){

return false;

} else {

st.push("a");

}

return st.empty();

}

};

花花酱 LeetCode 1002. Find Common Characters

By zxi on March 2, 2019

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

Example 1:

Input: ["bella","label","roller"]
Output: ["e","l","l"]

Example 2:

Input: ["cool","lock","cook"]
Output: ["c","o"]

Note:

1 <= A.length <= 100
1 <= A[i].length <= 100
A[i][j] is a lowercase letter

Solution: Min count for each character

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

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

vector<string> commonChars(vector<string>& A) {

vector<int> min_count(26, INT_MAX);

for (const string& a : A) {

vector<int> count(26, 0);

for (const char ch : a)

++count[ch - 'a'];

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

min_count[i] = min(min_count[i], count[i]);

}

vector<string> ans;

for (int i = 0; i < 26; ++i) {

if (min_count[i] == INT_MAX) continue;

for (int j = 0; j < min_count[i]; ++j)

ans.push_back(string(1, 'a' + i));

}

return ans;

}

};

花花酱 LeetCode 1004. Max Consecutive Ones III

By zxi on March 2, 2019

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Note:

1 <= A.length <= 20000
0 <= K <= A.length
A[i] is 0 or 1

Solution : Sliding Window

Maintain a window that has at most K zeros

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

C++

class Solution {

public:

int longestOnes(vector<int>& A, int K) {

int l = 0;

int zeros = 0;

int ans = 0;

for (int r = 0; r < A.size(); ++r) {

if (A[r] == 0) ++zeros;

while (zeros > K)

if (A[l++] == 0) --zeros;

ans = max(ans, r - l + 1);

}

return ans;

}

};

花花酱 LeetCode 30. Substring with Concatenation of All Words

By zxi on March 2, 2019

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in sthat is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

Solution1: HashTable + Brute Force

Time complexity: O((|S| – |W|*l) * |W|*l))
Space complexity: O(|W|*l)

C++

// Author: Huahua

// std::string_view running time: 128 ms, 16 MB

// std::string running time: 156 ms, 22.4 MB

class Solution {

public:

vector<int> findSubstring(string s, vector<string>& words) {

if (words.empty() || s.empty()) return {};

const int n = words.size();

const int l = words[0].length();

if (n * l > s.length()) return {};

std::string_view ss(s);

std::unordered_map<std::string_view, int> expected;

for (const string& word : words)

++expected[string_view(word)];

vector<int> ans;

for (int i = 0; i <= ss.length() - n * l; ++i) {

std::unordered_map<std::string_view, int> seen;

int count = 0;

for (int j = 0; j < n; ++j) {

std::string_view w = ss.substr(i + j * l, l);

auto it = expected.find(w);

if (it == expected.end()) break;

if (++seen[w] > it->second) break;

++count;

}

if (count == n)

ans.push_back(i);

}

return ans;

}

};

花花酱 LeetCode Weekly 125

By zxi on February 24, 2019

Huahua's Tech Road

花花酱 LeetCode 1003. Check If Word Is Valid After Substitutions

Solution: Stack

C++

花花酱 LeetCode 1002. Find Common Characters

Solution: Min count for each character

C++

花花酱 LeetCode 1004. Max Consecutive Ones III

Solution : Sliding Window

C++

花花酱 LeetCode 30. Substring with Concatenation of All Words

Solution1: HashTable + Brute Force

C++

花花酱 LeetCode Weekly 125

Problems