Posts tagged as “hashtable”

花花酱 LeetCode 791. Custom Sort String

By zxi on February 24, 2018

题目大意：给你字符的顺序，让你排序一个字符串。

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Example :

Input:

S = "cba"

T = "abcd"

Output: "cbad"

Explanation:

"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a".

Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.

Note:

S has length at most 26, and no character is repeated in S.
T has length at most 200.
S and T consist of lowercase letters only.

Solution 1: HashTable + Sorting

Store the order of char in a hashtable
Sort the string based on the order

Time complexity: O(nlogn)

Space complexity: O(128)

// Author: Huahua

// Running time: 2 ms

class Solution {

public:

string customSortString(string S, string T) {

vector<int> order(128, INT_MAX);

int i = 0;

for (char c: S)

if (order[c] == INT_MAX) order[c] = ++i;

std::sort(T.begin(), T.end(), [&order](const char c1, const char c2){

return order[c1] < order[c2];

});

return T;

}

};

花花酱 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 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 734. Sentence Similarity

By zxi on November 28, 2017

Problem:

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

For example, “great acting skills” and “fine drama talent” are similar, if the similar word pairs are pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]].

Note that the similarity relation is not transitive. For example, if “great” and “fine” are similar, and “fine” and “good” are similar, “great” and “good” are not necessarily similar.

However, similarity is symmetric. For example, “great” and “fine” being similar is the same as “fine” and “great” being similar.

Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.

Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].

Note:

The length of words1 and words2 will not exceed 1000.
The length of pairs will not exceed 2000.
The length of each pairs[i] will be 2.
The length of each words[i] and pairs[i][j] will be in the range [1, 20].

题目大意：

给你两个句子（由单词数组表示）和一些近义词对，问你这两个句子是否相似，即每组相对应的单词都要相似。

注意相似性不能传递，比如给只你”great”和”fine”相似、”fine”和”good”相似，这种情况下”great”和”good”不相似。

Idea:

Use hashtable to store mapping from word to its similar words.

Solution: HashTable

Time complexity: O(|pairs| + |words1|)

Space complexity: O(|pairs|)

C++

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

bool areSentencesSimilar(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs) {

if (words1.size() != words2.size()) return false;

unordered_map<string, unordered_set<string>> similar_words;

for (const auto& pair : pairs) {

similar_words[pair.first].insert(pair.second);

similar_words[pair.second].insert(pair.first);

}

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

if (words1[i] == words2[i]) continue;

if (!similar_words[words1[i]].count(words2[i])) return false;

}

return true;

}

};

Java

// Author: Huahua

// Runtime: 10 ms

class Solution {

public boolean areSentencesSimilar(String[] words1, String[] words2, String[][] pairs) {

if (words1.length != words2.length) return false;

Map<String, Set<String>> similar_words = new HashMap<>();

for (String[] pair : pairs) {

if (!similar_words.containsKey(pair[0]))

similar_words.put(pair[0], new HashSet<>());

if (!similar_words.containsKey(pair[1]))

similar_words.put(pair[1], new HashSet<>());

similar_words.get(pair[0]).add(pair[1]);

similar_words.get(pair[1]).add(pair[0]);

}

for (int i = 0; i < words1.length; ++i) {

if (words1[i].equals(words2[i])) continue;

if (!similar_words.containsKey(words1[i])) return false;

if (!similar_words.get(words1[i]).contains(words2[i])) return false;

}

return true;

}

Python

"""

Author: Huahua

Runtime: 62 ms

"""

class Solution:

def areSentencesSimilar(self, words1, words2, pairs):

if len(words1) != len(words2): return False

similar_words = {}

for w1, w2 in pairs:

if not w1 in similar_words: similar_words[w1] = set()

if not w2 in similar_words: similar_words[w2] = set()

similar_words[w1].add(w2)

similar_words[w2].add(w1)

for w1, w2 in zip(words1, words2):

if w1 == w2: continue

if w1 not in similar_words: return False

if w2 not in similar_words[w1]: return False

return True

Related Problems:

[解题报告] LeetCode 737. Sentence Similarity II

花花酱 LeetCode 1. Two Sum

By zxi on November 23, 2017

Problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Idea:

Brute force / Hashtable

Solution1:

Brute force / C++

Time complexity: O(n^2)

Space complexity: O(1)

// Author: Huahua

// Runtime: 166 ms

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

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

for (int j = i + 1;j < nums.size(); ++j) {

int sum = nums[i] + nums[j];

if (sum == target) {

return {i, j};

}

return {};

}

};

Solution 2:

Hashtable / C++

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> indies;

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

indies[nums[i]] = i;

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

int left = target - nums[i];

if (indies.count(left) && indies[left] != i) {

return {i, indies[left]};

}

return {};

}

};