Posts published in “Hashtable”

花花酱 LeetCode 771. Jewels and Stones

By zxi on February 2, 2018

题目大意：给你宝石的类型，再给你一堆石头，返回里面宝石的数量。

Problem:

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

S and J will consist of letters and have length at most 50.
The characters in J are distinct.

Solution 1: HashTable

Time complexity: O(|J| + |S|)

Space complexity: O(128) / O(|J|)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int numJewelsInStones(string J, string S) {

std::vector<int> f(128, 0);

int ans = 0;

for (const char j : J)

f[j] = 1;

for (const char s : S)

ans += f[s] & 1;

return ans;

}

};

C++ v2

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

int numJewelsInStones(const string& J, const string& S) {

std::set<char> f(J.begin(), J.end());

return std::count_if(S.begin(), S.end(),

[&f](const char c) { return f.count(c); });

}

};

Java

// Author: Huahua

// Running time: 18 ms

class Solution {

public int numJewelsInStones(String J, String S) {

int[] f = new int[128];

for (final char c : J.toCharArray())

f[c] = 1;

int ans = 0;

for (final char c : S.toCharArray())

ans += f[c];

return ans;

}

Python

"""

Author: Huahua

Running time: 43 ms

"""

class Solution(object):

def numJewelsInStones(self, J, S):

f = set(J)

return sum([s in f for s in S])

花花酱 LeetCode 758. Bold Words in String

By zxi on January 8, 2018

题目大意：给你一个字符串和一些要加粗的单词，返回加粗后的HTML代码。

Problem:

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between  and  tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "aabcd". Note that returning "aabcd" would use more tags, so it is incorrect.

Note:

words has length in range [0, 50].
words[i] has length in range [1, 10].
S has length in range [0, 500].
All characters in words[i] and S are lowercase letters.

Solution:

C++

Time complexity: O(nL^2)

Space complexity: O(n + d)

d: size of dictionary

L: max length of the word which is 10.

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

string boldWords(vector<string>& words, string S) {

const int kMaxWordLen = 10;

unordered_set<string> dict(words.begin(), words.end());

int n = S.length();

vector<int> bolded(n, 0);

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

for (int l = 1; l <= min(n - i, kMaxWordLen); ++l)

if (dict.count(S.substr(i, l)))

std::fill(bolded.begin() + i, bolded.begin() + i + l, 1);

string ans;

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

if (bolded[i] && (i == 0 || !bolded[i - 1])) ans += "";

ans += S[i];

if (bolded[i] && (i == n - 1 || !bolded[i + 1])) ans += "";

}

return ans;

}

};

花花酱 LeetCode 760. Find Anagram Mappings

By zxi on January 8, 2018

题目大意：输出数组A中每个元素在数组B中的索引。

Given two lists Aand B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order of the elements in A.

We want to find an index mapping P, from A to B. A mapping P[i] = j means the ith element in A appears in B at index j.

These lists A and B may contain duplicates. If there are multiple answers, output any of them.

For example, given

1 2	A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28]

We should return

1	[1, 4, 3, 2, 0]

as P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of Aappears at B[4], and so on.

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> anagramMappings(vector<int>& A, vector<int>& B) {

map<int, int> indices;

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

indices[B[i]] = i;

vector<int> ans;

for (const int a : A)

ans.push_back(indices[a]);

return ans;

}

};

C++ / No duplication

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> anagramMappings(vector<int>& A, vector<int>& B) {

map<int, vector<int>> indices;

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

indices[B[i]].push_back(i);

vector<int> ans;

for (const int a : A) {

ans.push_back(indices[a].back());

indices[a].pop_back();

}

return ans;

}

};

花花酱 LeetCode 748. Shortest Completing Word

By zxi on December 20, 2017

题目大意: 给你一个由字母和数字组成车牌。另外给你一些单词，让你找一个最短的单词能够覆盖住车牌中的字母（不考虑大小写）。如果有多个解，输出第一个解。

Problem:

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate

Here, for letters we ignore case. For example, "P" on the licensePlate still matches "p" on the word.

It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of "PP", the word "pair" does not complete the licensePlate, but the word "supper" does.

Example 1:

Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]

Output: "steps"

Explanation: The smallest length word that contains the letters "S", "P", "S", and "T".

Note that the answer is not "step", because the letter "s" must occur in the word twice.

Also note that we ignored case for the purposes of comparing whether a letter exists in the word.

Example 2:

Input: licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]

Output: "pest"

Explanation: There are 3 smallest length words that contains the letters "s".

We return the one that occurred first.

Note:

licensePlate will be a string with length in range [1, 7].
licensePlate will contain digits, spaces, or letters (uppercase or lowercase).
words will have a length in the range [10, 1000].
Every words[i] will consist of lowercase letters, and have length in range [1, 15].

Idea:

Hashtable

Solution:

C++

Time complexity: 时间复杂度 O(N*26), N is number of words.

Space complexity: 空间复杂度 O(26) = O(1)

// Author: Huahua

// Runtime: 15 ms

class Solution {

public:

string shortestCompletingWord(string licensePlate, vector<string>& words) {

vector<int> l(26, 0);

for (const char ch : licensePlate)

if (isalpha(ch)) ++l[tolower(ch) - 'a'];

string ans;

int min_l = INT_MAX;

for (const string& word : words) {

if (word.length() >= min_l) continue;

if (!matches(l, word)) continue;

min_l = word.length();

ans = word;

}

return ans;

}

private:

bool matches(const vector<int>& l, const string& word) {

vector<int> c(26, 0);

for (const char ch : word)

++c[tolower(ch) - 'a'];

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

if (c[i] < l[i]) return false;

return true;

}

};

花花酱 LeetCode 745. Prefix and Suffix Search

By zxi on December 11, 2017

Link: https://leetcode.com/problems/prefix-and-suffix-search/description/

Problem:

Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.

Examples:

Input:

WordFilter(["apple"])

WordFilter.f("a", "e") // returns 0

WordFilter.f("b", "") // returns -1

Note:

words has length in range [1, 15000].
For each test case, up to words.length queries WordFilter.f may be made.
words[i] has length in range [1, 10].
prefix, suffix have lengths in range [0, 10].
words[i] and prefix, suffix queries consist of lowercase letters only.

Idea:

Construct all possible filters

Solution1:

C++

Time complexity: O(NL^3 + QL) where N is the number of words, L is the max length of the word, Q is the number of queries.

Space complexity: O(NL^3)

// Author: Huahua

// Runtime: 482 ms

class WordFilter {

public:

WordFilter(const vector<string>& words) {

int index = 0;

for (const string& word : words) {

int n = word.length();

string prefix;

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

if (i > 0) prefix += word[i - 1];

string suffix;

for (int j = n; j >= 0; --j) {

if (j != n) suffix = word[j] + suffix;

const string key = prefix + "_" + suffix;

filters_[key] = index;

}

++index;

}

int f(string prefix, string suffix) {

const string key = prefix + "_" + suffix;

auto it = filters_.find(key);

if (it != filters_.end()) return it->second;

return -1;

}

private:

unordered_map<string, int> filters_;

};

Version #2

// Author: Huahua

// Runtime: 499 ms

class WordFilter {

public:

WordFilter(const vector<string>& words) {

int index = 0;

for (const string& word : words) {

int n = word.length();

vector<string> prefixes(n + 1, "");

vector<string> suffixes(n + 1, "");

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

prefixes[i + 1] = prefixes[i] + word[i];

suffixes[i + 1] = word[n - i - 1] + suffixes[i];

}

for (const string& prefix : prefixes)

for (const string& suffix : suffixes)

filters_[prefix + "_" + suffix] = index;

++index;

}

int f(string prefix, string suffix) {

const string key = prefix + "_" + suffix;

auto it = filters_.find(key);

if (it != filters_.end()) return it->second;

return -1;

}

private:

unordered_map<string, int> filters_;

};

Solution 2:

C++ / Trie

Time complexity: O(NL^2 + QL) where N is the number of words, L is the max length of the word, Q is the number of queries.

Space complexity: O(NL^2)

// Author: Huahua

// Runtime: 572 ms

class Trie {

public:

/** Initialize your data structure here. */

Trie(): root_(new TrieNode()) {}

/** Inserts a word into the trie. */

void insert(const string& word, int index) {

TrieNode* p = root_.get();

for (const char c : word) {

if (!p->children[c - 'a'])

p->children[c - 'a'] = new TrieNode();

p = p->children[c - 'a'];

// Update index

p->index = index;

}

p->is_word = true;

}

/** Returns the index of word that has the prefix. */

int startsWith(const string& prefix) const {

auto node = find(prefix);

if (!node) return -1;

return node->index;

}

private:

struct TrieNode {

TrieNode():index(-1), is_word(false), children(27, nullptr){}

~TrieNode() {

for (TrieNode* child : children)

if (child) delete child;

}

int index;

int is_word;

vector<TrieNode*> children;

};

const TrieNode* find(const string& prefix) const {

const TrieNode* p = root_.get();

for (const char c : prefix) {

p = p->children[c - 'a'];

if (p == nullptr) break;

}

return p;

}

std::unique_ptr<TrieNode> root_;

};

class WordFilter {

public:

WordFilter(vector<string> words) {

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

const string& w = words[i];

string key = "{" + w;

trie_.insert(key, i);

for (int j = 0; j < w.size(); ++j) {

key = w[w.size() - j - 1] + key;

trie_.insert(key, i);

}

int f(string prefix, string suffix) {

return trie_.startsWith(suffix + "{" + prefix);

}

private:

Trie trie_;

};

Related Problems: