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;

}

};

Problem

题目大意：对一个string进行in-place的run length encoding。

https://leetcode.com/problems/string-compression/description/

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

Note:

All characters have an ASCII value in [35, 126].
1 <= len(chars) <= 1000.

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int compress(vector<char>& chars) {

const int n = chars.size();

int p = 0;

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

int count = 1;

while (i < n && chars[i] == chars[i - 1]) { ++i; ++count; }

chars[p++] = chars[i - 1];

if (count == 1) continue;

for (char c : to_string(count))

chars[p++] = c;

}

return p;

}

};

Posts tagged as “compression”

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

Solution: Subsets

C++

花花酱 LeetCode 443. String Compression

Problem

Solution