Huahua’s Tech Road

花花酱 LeetCode 676. Implement Magic Dictionary

By zxi on September 10, 2017

Problem:

Implement a magic directory with buildDict, and search methods.

For the method buildDict, you’ll be given a list of non-repetitive words to build a dictionary.

For the method search, you’ll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.

Example 1:

Input: buildDict(["hello", "leetcode"]), Output: Null

Input: search("hello"), Output: False

Input: search("hhllo"), Output: True

Input: search("hell"), Output: False

Input: search("leetcoded"), Output: False

Note:

You may assume that all the inputs are consist of lowercase letters a-z.
For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see here for more details.

Idea:

Fuzzy match

Time Complexity:

buildDict: O(n*m)

n: numbers of words

m: length of word

search: O(m)

m: length of word

Space Complexity:

O(n*m)

Solution:

// Author: Huahua

class MagicDictionary {

public:

/** Initialize your data structure here. */

MagicDictionary() {

dict_.clear();

}

/** Build a dictionary through a list of words */

void buildDict(vector<string> dict) {

for(string& word: dict) {

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

char c = word[i];

word[i] = '*';

dict_[word].insert(c);

word[i] = c;

}

/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */

bool search(string word) {

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

char c = word[i];

word[i] = '*';

if (dict_.count(word)) {

const auto& char_set = dict_[word];

if (!char_set.count(c) || char_set.size() > 1)

return true;

}

word[i] = c;

}

return false;

}

private:

unordered_map<string, unordered_set<char>> dict_;

};

/**

* Your MagicDictionary object will be instantiated and called as such:

* MagicDictionary obj = new MagicDictionary();

* obj.buildDict(dict);

* bool param_2 = obj.search(word);

Java / Trie

class MagicDictionary {

private Trie root;

public MagicDictionary() {

root = new Trie();

}

public void buildDict(String[] dict) {

for (String word : dict) {

Trie curr = root;

for (char c : word.toCharArray()) {

int index = c - 'a';

if (curr.children[index] == null)

curr.children[index] = new Trie();

curr = curr.children[index];

}

curr.ends = true;

}

public boolean search(String word) {

char[] s = word.toCharArray();

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

for (char c = 'a'; c <= 'z'; ++c) {

if (s[i] == c) continue;

char tmp = s[i];

s[i] = c;

if (contains(s)) return true;

s[i] = tmp;

}

return false;

}

private boolean contains(char[] word) {

Trie curr = root;

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

curr = curr.children[word[i] - 'a'];

if (curr == null) return false;

}

return curr.ends;

}

class Trie {

private boolean ends;

private Trie[] children;

public Trie() {

children = new Trie[26];

ends = false;

}

Java / Trie v2

class MagicDictionary {

private Trie root;

public MagicDictionary() {

root = new Trie();

}

public void buildDict(String[] dict) {

for (String word : dict) {

Trie curr = root;

for (char c : word.toCharArray()) {

int index = c - 'a';

if (curr.children[index] == null)

curr.children[index] = new Trie();

curr = curr.children[index];

}

curr.ends = true;

}

public boolean search(String word) {

char[] s = word.toCharArray();

Trie prefix = root;

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

for (char c = 'a'; c <= 'z'; ++c) {

if (s[i] == c) continue;

char tmp = s[i];

s[i] = c;

if (contains(s, prefix, i)) return true;

s[i] = tmp;

}

prefix = prefix.children[s[i] - 'a'];

if (prefix == null) return false;

}

return false;

}

private boolean contains(char[] word, Trie prefix, int s) {

Trie curr = prefix;

for (int i = s; i < word.length; ++i) {

curr = curr.children[word[i] - 'a'];

if (curr == null) return false;

}

return curr.ends;

}

class Trie {

private boolean ends;

private Trie[] children;

public Trie() {

children = new Trie[26];

ends = false;

}

花花酱 LeetCode 300. Longest Increasing Subsequence

By zxi on September 10, 2017

Problem:

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Idea:

Dynamic Programming

Time Complexity:

O(n^2)

Solution 1:

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

if (nums.empty()) return 0;

int n = nums.size();

auto f = vector<int>(n, 1);

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

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

if (nums[i] > nums[j])

f[i] = max(f[i], f[j] + 1);

return *max_element(f.begin(), f.end());

}

};

Solution 2: DP + Binary Search / Patience Sort

dp[i] := smallest tailing number of a increasing subsequence of length i + 1.

dp is an increasing array, we can use binary search to find the index to insert/update the array.

ans = len(dp)

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

C++

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

const int n = nums.size();

if (n == 0) return 0;

vector<int> dp;

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

auto it = lower_bound(begin(dp), end(dp), nums[i]);

if (it == end(dp))

dp.push_back(nums[i]);

else

*it = nums[i];

}

return dp.size();

}

};

Python3

class Solution:

def lengthOfLIS(self, nums: List[int]) -> int:

d = []

for x in nums:

i = bisect_left(d, x)

if i == len(d):

d.append(x)

else:

d[i] = x

return len(d)

Related Problems:

花花酱 LeetCode 674. Longest Continuous Increasing Subsequence

By zxi on September 10, 2017

Problem:

Given an unsorted array of integers, find the length of longest continuous increasing subsequence.

Example 1:

1 2	Input: [1,3,5,4,7] Output: 3

Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] is also an increasing subsequence, it’s not a continuous one where 5 and 7 are separated by 4.

Example 2:

1 2	Input: [2,2,2,2,2] Output: 1

Explanation: The longest continuous increasing subsequence is [2], its length is 1.

Note: Length of the array will not exceed 10,000.

Idea:

Dynamic Programming

Solution:

// Author: Huahua

class Solution {

public:

int findLengthOfLCIS(vector<int>& nums) {

if (nums.empty()) return 0;

int cur = 1;

int ans = 1;

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

if (nums[i] > nums[i-1]) {

++cur;

ans = max(ans, cur);

} else {

cur = 1;

}

return ans;

}

};

花花酱 LeetCode 63. Unique Paths II

By zxi on September 9, 2017

Problem:

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3×3 grid as illustrated below.

Idea:

Dynamic Programming

Solution:

class Solution {

public:

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

int n = obstacleGrid.size();

if (n == 0) return 0;

int m = obstacleGrid[0].size();

// f[i][j] = paths(i, j)

// INT_MIN -> not solved yet, solution unknown

f_ = vector<vector<int>>(n + 1, vector<int>(m + 1, INT_MIN));

return paths(m, n, obstacleGrid);

}

private:

vector<vector<int>> f_;

int paths(int x, int y, const vector<vector<int>>& o) {

// Out of bound, return 0.

if (x <= 0 || y <= 0) return 0;

// Reaching the starting point.

// Note, there might be an obstacle here as well.

if (x == 1 && y == 1) return 1 - o[0][0];

// Already solved, return the answer.

if (f_[y][x] != INT_MIN) return f_[y][x];

// There is an obstacle on current block, no path

if (o[y - 1][x - 1] == 1) {

f_[y][x] = 0;

} else {

// Recursively find paths.

f_[y][x] = paths(x - 1, y, o) + paths(x, y - 1, o);

}

// Return the memorized answer.

return f_[y][x];

}

};

Related Problems:

[解题报告] LeetCode 62. Unique Paths

花花酱 LeetCode 62. Unique Paths

By zxi on September 9, 2017

Problem:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Idea:

Dynamic Programming

Solution1:

C++

// Author: Huahua

class Solution {

public:

int uniquePaths(int m, int n) {

if (m < 0 || n < 0) return 0;

if (m == 1 && n == 1) return 1;

if (f_[m][n] > 0) return f_[m][n];

int left_paths = uniquePaths(m - 1, n);

int top_paths = uniquePaths(m, n - 1);

f_[m][n] = left_paths + top_paths;

return f_[m][n];

}

private:

unordered_map<int, unordered_map<int, int>> f_;

};

Java

// Author: Huahua

// Running time: 0 ms

class Solution {

private int[][] dp;

private int m;

private int n;

public int uniquePaths(int m, int n) {

this.dp = new int[m][n];

this.m = m;

this.n = n;

return dfs(0, 0);

}

private int dfs(int x, int y) {

if (x > m - 1 || y > n - 1)

return 0;

if (x == m - 1 && y == n - 1)

return 1;

if (dp[x][y] == 0)

dp[x][y] = dfs(x + 1, y) + dfs(x , y + 1);

return dp[x][y];

}

Solution2:

// Author: Huahua

class Solution {

public:

int uniquePaths(int m, int n) {

auto f = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));

f[1][1] = 1;

for (int y = 1; y <= n; ++y)

for(int x = 1; x <= m; ++x) {

if (x == 1 && y == 1) {

continue;

} else {

f[y][x] = f[y-1][x] + f[y][x-1];

}

return f[n][m];

}

};

Huahua's Tech Road

花花酱 LeetCode 676. Implement Magic Dictionary

花花酱 LeetCode 300. Longest Increasing Subsequence

C++

Python3

花花酱 LeetCode 674. Longest Continuous Increasing Subsequence

花花酱 LeetCode 63. Unique Paths II

花花酱 LeetCode 62. Unique Paths