Posts published in “Hashtable”

花花酱 LeetCode 1178. Number of Valid Words for Each Puzzle

By zxi on September 1, 2019

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

word contains the first letter of puzzle.
For each letter in word, that letter is in puzzle.
For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”; while invalid words are “beefed” (doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

Example :

Input: 
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

Constraints:

1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] are English lowercase letters.
Each puzzles[i] doesn’t contain repeated characters.

Solution: Subsets

Preprocessing:
Compress each word to a bit map, and compute the frequency of each bit map.
Since there are at most |words| bitmaps while its value ranging from 0 to 2^26, thus it’s better to use a hashtable instead of an array.

Query:
Use the same way to compress a puzzle into a bit map.
Try all subsets (at most 128) of the puzzle (the bit of the first character is be must), and check how many words match each subset.

words = [“aaaa”,”asas”,”able”,”ability”,”actt”,”actor”,”access”],
puzzle = “abslute”
bitmap(“aaaa”) = {0}
bitmap(“asas”) = {0, 18}
bitmap(“able”) = {0,1,4,11}
bitmap(“actt”) = {0, 2, 19}
bitmap(“actor”) = {0, 2, 14, 17, 19}
bitmap(“access”) = {0, 2, 4, 18}

bitmap(“abslute”) = {0, 1, 4, 11, 18, 19, 20}

Time complexity: O(sum(len(w_i)) + |puzzles|)
Space complexity: O(|words|)

C++

// Author: Huahua, 136 ms, 29.7 MB

class Solution {

public:

vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {

vector<int> ans;

unordered_map<int, int> freq;

for (const string& word : words) {

int mask = 0;

for (char c : word)

mask |= 1 << (c - 'a');

++freq[mask];

}

for (const string& p : puzzles) {

int mask = 0;

for (char c : p)

mask |= 1 << (c - 'a');

int first = p[0] - 'a';

int curr = mask;

int total = 0;

while (curr) {

if ((curr >> first) & 1) {

auto it = freq.find(curr);

if (it != freq.end()) total += it->second;

}

curr = (curr - 1) & mask;

}

ans.push_back(total);

}

return ans;

}

};

花花酱 LeetCode 1177. Can Make Palindrome from Substring

By zxi on September 1, 2019

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], ..., s[right], and then choose up to k of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return an array answer[], where answer[i] is the result of the i-th query queries[i].

Note that: Each letter is counted individually for replacement so if for example s[left..right] = "aaa", and k = 2, we can only replace two of the letters. (Also, note that the initial string s is never modified by any query.)

Example :

Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0] : substring = "d", is palidrome.
queries[1] : substring = "bc", is not palidrome.
queries[2] : substring = "abcd", is not palidrome after replacing only 1 character.
queries[3] : substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4] : substring = "abcda", could be changed to "abcba" which is palidrome.

Constraints:

1 <= s.length, queries.length <= 10^5
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s only contains lowercase English letters.

Solution: Prefix frequency

Compute the prefix frequency of each characters, then we can efficiently compute the frequency of each characters in the substring in O(1) time. Count the number odd frequency characters o, we can convert it to a palindrome if o / 2 <= k.

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

C++

// Author: Huahua

class Solution {

public:

vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {

vector<bool> ans;

int n = s.length();

vector<vector<int>> f(n + 1, vector<int>(26));

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

++f[i][s[i] - 'a'];

f[i + 1] = f[i];

}

for (const auto& q : queries) {

int l = q[0];

int r = q[1];

int k = q[2];

int o = 0;

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

int c = f[r][i] - (l == 0 ? 0 : f[l - 1][i]);

o += c % 2;

}

ans.push_back(o / 2 <= k);

}

return ans;

}

};

花花酱 LeetCode 36. Valid Sudoku

By zxi on August 20, 2019

Determine if a 9×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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["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:
[
  ["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.

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.
The given board contain only digits 1-9 and the character '.'.
The given board size is always 9x9.

Solution: HashTable

Use hashtable to store the numbers of each row, column and each 3×3 box. If there number appears more than once then it’s an invalid Sudoku.

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

C++

// Author: Huahua

class Solution {

public:

bool isValidSudoku(vector<vector<char> > &board) {

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

set<char> r, c;

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

if (board[i][j] != '.' && !r.insert(board[i][j]).second)

return false;

if (board[j][i] != '.' && !c.insert(board[j][i]).second)

return false;

}

for (int p = 0; p < 3; p++)

for (int q = 0; q < 3; q++) {

set<char> b;

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

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

int x = p * 3 + i;

int y = q * 3 + j;

if (board[y][x] != '.' && !b.insert(board[y][x]).second)

return false;

}

return true;

}

};

Follow up:

https://zxi.mytechroad.com/blog/searching/leetcode-37-sudoku-solver/

花花酱 LeetCode 1160. Find Words That Can Be Formed by Characters

By zxi on August 17, 2019

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Note:

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
All strings contain lowercase English letters only.

Solution: Hashtable

Use a hashtable to store each letter’s frequency of the string and compare that with each word.

Time complexity: O(n + sum(len(word))
Space complexity: O(1)

C++

// Author: Huahua, 72 ms, 20 MB

class Solution {

public:

int countCharacters(vector<string>& words, string chars) {

vector<int> counts(26);

for (char c : chars) ++counts[c - 'a'];

int ans = 0;

for (const string& word : words) {

vector<int> cur(26);

bool valid = true;

for (char c: word)

if (++cur[c - 'a'] > counts[c - 'a']) {

valid = false;

break;

}

if (valid) ans += word.length();

}

return ans;

}

};

Python#

# Author: Huahua

class Solution:

def countCharacters(self, words: List[str], chars: str) -> int:

counts = collections.Counter(chars)

def isValid(word):

cur = collections.Counter(word)

for c in cur:

if c not in counts or cur[c] > counts[c]:

return False

return True

ans = 0

for word in words:

ans += len(word) if isValid(word) else 0

return ans

花花酱 LeetCode 1156. Swap For Longest Repeated Character Substring

By zxi on August 11, 2019

Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.

Example 1:

Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa", which its length is 3.

Example 2:

Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa", which its length is 6.

Example 3:

Input: text = "aaabbaaa"
Output: 4

Example 4:

Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa", length is 5.

Example 5:

Input: text = "abcdef"
Output: 1

Constraints:

1 <= text.length <= 20000
text consist of lowercase English characters only.

Solution: HashTable

Pre-processing

Compute the longest repeated substring starts and ends with text[i].
Count the frequency of each letter.

Main

Loop through each letter
Check the left and right letter
- if they are the same, len = left + right
  - e.g1. “aa c aaa [b] aaaa” => len = 3 + 4 = 7
- if they are not the same, len = max(left, right)
  - e.g2. “aa [b] ccc d c” => len = max(2, 3) = 3
If the letter occurs more than len times, we can always find an extra one and swap it with the current letter => ++len
- e.g.1, count[“a”] = 9 > 7, len = 7 + 1 = 8
- e.g.2, count[“c”] = 4 > 3, len = 3 + 1 = 4

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

C++

// Author: Huahua

class Solution {

public:

int maxRepOpt1(string text) {

int n = text.length();

// Length of repeted substring ends with text[i]

vector<vector<int>> len1(n, vector<int>(26));

// Length of repeated substring starts with text[i]

vector<vector<int>> len2(n, vector<int>(26));

vector<int> counts(26);

int last = -1; // not a letter

int l = 0;

int ans = 0;

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

const int c = text[i] - 'a';

if (c == last) {

++l;

} else {

last = c;

l = 1;

}

len1[i][c] = l;

len2[i - l + 1][c] = l;

++counts[c];

ans = max(ans, l);

}

for (int i = 1; i < n - 1; ++i) {

int cl = text[i - 1] - 'a';

int cr = text[i + 1] - 'a';

int left = len1[i - 1][cl];

int right = len2[i + 1][cr];

int count = 0;

if (cl != cr) {

// e.g. "c aaa b cccc" => "b aaa ccccc"

count = max(left + (counts[cl] > left ? 1 : 0),

right + (counts[cr] > right ? 1 : 0));

} else {

// e.g. "a c aaa b aaaa" => "b c aaaaaaaa"

count = left + right;

if (counts[cl] > count) ++count;

}

ans = max(ans, count);

}

return ans;

}

};