花花酱 LeetCode 110. Balanced Binary Tree

By zxi on September 3, 2017

Solution 1: O(nlogn)

// Author: Huahua

// O(nlogn)

class Solution {

Solution 1: O(nlogn)

public:

bool isBalanced(TreeNode* root) {

if(!root) return true;

int left_height = height(root->left);

int right_height = height(root->right);

return (abs(left_height - right_height)<=1) && isBalanced(root->left) && isBalanced(root->right);

}

private:

int height(TreeNode* root) {

if(!root) return 0;

return max(height(root->left), height(root->right))+1;

}

};

Solution 2: O(n)

// Author: Huahua

// O(n)

class Solution {

public:

bool isBalanced(TreeNode* root) {

if(!root) return true;

bool balanced = true;

height(root, &balanced);

return balanced;

}

private:

int height(TreeNode* root, bool* balanced) {

if(!root) return 0;

int left_height = height(root->left, balanced);

if(!balanced) return -1;

int right_height = height(root->right, balanced);

if(!balanced) return -1;

if(abs(left_height-right_height)>1) {

*balanced = false;

return -1;

}

return max(left_height, right_height) + 1;

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

private boolean balanced;

private int height(TreeNode root) {

if (root == null || !this.balanced) return -1;

int l = height(root.left);

int r = height(root.right);

if (Math.abs(l - r) > 1) {

this.balanced = false;

return -1;

}

return Math.max(l, r) + 1;

}

public boolean isBalanced(TreeNode root) {

this.balanced = true;

height(root);

return this.balanced;

}

Python

"""

Author: Huahua

Running time: 76 ms

"""

class Solution:

def isBalanced(self, root):

self.balanced = True

def height(root):

if not root or not self.balanced: return -1

l = height(root.left)

r = height(root.right)

if abs(l - r) > 1:

self.balanced = False

return -1

return max(l, r) + 1

height(root)

return self.balanced

花花酱 Leetcode 140. Word Break II

By zxi on September 2, 2017

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution

Time complexity: O(2^n)

Space complexity: O(2^n)

C++

// Author: Huahua

class Solution {

public:

vector<string> wordBreak(string s, vector<string>& wordDict) {

unordered_set<string> dict(wordDict.cbegin(), wordDict.cend());

return wordBreak(s, dict);

}

private:

// >> append({"cats and", "cat sand"}, "dog");

// {"cats and dog", "cat sand dog"}

vector<string> append(const vector<string>& prefixes, const string& word) {

vector<string> results;

for(const auto& prefix : prefixes)

results.push_back(prefix + " " + word);

return results;

}

const vector<string>& wordBreak(string s, unordered_set<string>& dict) {

// Already in memory, return directly

if(mem_.count(s)) return mem_[s];

// Answer for s

vector<string> ans;

// s in dict, add it to the answer array

if(dict.count(s))

ans.push_back(s);

for(int j=1;j<s.length();++j) {

// Check whether right part is a word

const string& right = s.substr(j);

if (!dict.count(right)) continue;

// Get the ans for left part

const string& left = s.substr(0, j);

const vector<string> left_ans =

append(wordBreak(left, dict), right);

// Notice, can not use mem_ here,

// since we haven't got the ans for s yet.

ans.insert(ans.end(), left_ans.begin(), left_ans.end());

}

// memorize and return

mem_[s].swap(ans);

return mem_[s];

}

private:

unordered_map<string, vector<string>> mem_;

};

Python3

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def wordBreak(self, s, wordDict):

words = set(wordDict)

mem = {}

def wordBreak(s):

if s in mem: return mem[s]

ans = []

if s in words: ans.append(s)

for i in range(1, len(s)):

right = s[i:]

if right not in words: continue

ans += [w + " " + right for w in wordBreak(s[0:i])]

mem[s] = ans

return mem[s]

return wordBreak(s)

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Idea:

Time complexity O(n^2)

Space complexity O(n^2)

Solutions:

C++

// Author: Huahua

class Solution {

public:

bool wordBreak(string s, vector<string>& wordDict) {

// Create a hashset of words for fast query.

unordered_set<string> dict(wordDict.cbegin(), wordDict.cend());

// Query the answer of the original string.

return wordBreak(s, dict);

}

bool wordBreak(const string& s, const unordered_set<string>& dict) {

// In memory, directly return.

if(mem_.count(s)) return mem_[s];

// Whole string is a word, memorize and return.

if(dict.count(s)) return mem_[s]=true;

// Try every break point.

for(int j=1;j<s.length();j++) {

const string left = s.substr(0,j);

const string right = s.substr(j);

// Find the solution for s.

if(dict.count(right) && wordBreak(left, dict))

return mem_[s]=true;

}

// No solution for s, memorize and return.

return mem_[s]=false;

}

private:

unordered_map<string, bool> mem_;

};

C++ V2 without using dict. Updated: 1/9/2018

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

bool wordBreak(string s, vector<string>& wordDict) {

// Mark evert word as breakable.

for (const string& word : wordDict)

mem_.emplace(word, true);

// Query the answer of the original string.

return wordBreak(s);

}

bool wordBreak(const string& s) {

// In memory, directly return.

if (mem_.count(s)) return mem_[s];

// Try every break point.

for (int j = 1; j < s.length(); j++) {

auto it = mem_.find(s.substr(j));

// Find the solution for s.

if (it != mem_.end() && it->second && wordBreak(s.substr(0, j)))

return mem_[s] = true;

}

// No solution for s, memorize and return.

return mem_[s] = false;

}

private:

unordered_map<string, bool> mem_;

};

Java

// Author: Huahua

// Runtime: 13 ms

class Solution {

public boolean wordBreak(String s, List<String> wordDict) {

Set<String> dict = new HashSet<String>(wordDict);

Map<String, Boolean> mem = new HashMap<String, Boolean>();

return wordBreak(s, mem, dict);

}

private boolean wordBreak(String s,

Map<String, Boolean> mem,

Set<String> dict) {

if (mem.containsKey(s)) return mem.get(s);

if (dict.contains(s)) {

mem.put(s, true);

return true;

}

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

if (dict.contains(s.substring(i)) && wordBreak(s.substring(0, i), mem, dict)) {

mem.put(s, true);

return true;

}

mem.put(s, false);

return false;

}

Python

"""

Author: Huahua

Runtime: 42 ms

"""

class Solution(object):

def wordBreak(self, s, wordDict):

def canBreak(s, m, wordDict):

if s in m: return m[s]

if s in wordDict:

m[s] = True

return True

for i in range(1, len(s)):

r = s[i:]

if r in wordDict and canBreak(s[0:i], m, wordDict):

m[s] = True

return True

m[s] = False

return False

return canBreak(s, {}, set(wordDict))

花花酱 Leetcode 100. Same Tree

By zxi on September 2, 2017

Problem:

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool isSameTree(TreeNode* p, TreeNode* q) {

// Both are emtry: same

if (!p && !q) return true;

// One is emtry: not the Same

if (!p || !q) return false;

// Both are not emptry, compare the root value

if (p->val != q->val) return false;

// Compare left-subtree and right-subtree recursively.

return isSameTree(p->left, q->left)

&& isSameTree(p->right, q->right);

}

};

Java

// Author: Huahua

class Solution {

public boolean isSameTree(TreeNode p, TreeNode q) {

if (p == null && q == null) return true;

if (p == null || q == null) return false;

return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

}

Python3

"""

Author: Huahua

"""

class Solution:

def isSameTree(self, p, q):

if not p and not q: return True

if not p or not q: return False

return all((p.val == q.val,

self.isSameTree(p.left, q.left),

self.isSameTree(p.right, q.right)))

Follow Up

花花酱 LeetCode 572. Subtree of Another Tree

花花酱 LeetCode 110. Balanced Binary Tree

花花酱 Leetcode 140. Word Break II

Problem

Solution

Related Problems

花花酱 Leetcode 139. Word Break

Problem

Idea:

Solutions:

花花酱 Leetcode 100. Same Tree

Problem:

Example 1:

Example 2:

Example 3:

Solution: Recursion

C++

Java

Python3

Follow Up

Huahua's Tech Road

花花酱 LeetCode 21: Merge Two Sorted Lists

花花酱 LeetCode 110. Balanced Binary Tree

花花酱 Leetcode 140. Word Break II

Problem

Solution

Related Problems

花花酱 Leetcode 139. Word Break

Problem

Idea:

Solutions:

花花酱 Leetcode 100. Same Tree

Problem:

Example 1:

Example 2:

Example 3:

Solution: Recursion

C++

Java

Python3

Follow Up