花花酱 LeetCode 241. Different Ways to Add Parentheses

By zxi on September 3, 2017

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

Input: "2-1-1".

1 2	((2-1)-1) = 0 (2-(1-1)) = 2

Output: [0, 2]

Example 2:

Input: "2*3-4*5"

(2*(3-(4*5))) = -34

((2*3)-(4*5)) = -14

((2*(3-4))*5) = -10

(2*((3-4)*5)) = -10

(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Solution:

Running time: 3ms

C++

// Author: Huahua

namespace huahua {

int add(int a, int b) { return a+b; }

int minus(int a, int b) { return a-b; }

int multiply(int a, int b) { return a*b; }

} // namespace huahua

class Solution {

public:

vector<int> diffWaysToCompute(string input) {

return ways(input);

}

private:

const vector<int>& ways(const string& input) {

// Already solved, return the answer

if(m_.count(input)) return m_[input];

// Array for answer of input

vector<int> ans;

// Break the expression at every operator

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

char op = input[i];

// Split the input by an op

if(op=='+' || op=='-' || op=='*') {

const string left = input.substr(0, i);

const string right = input.substr(i+1);

// Get the solution of left/right sub-expressions

const vector<int>& l = ways(left);

const vector<int>& r = ways(right);

std::function<int(int,int)> f;

switch(op) {

case '+': f = huahua::add; break;

case '-': f = huahua::minus; break;

case '*': f = huahua::multiply; break;

}

// Combine the solution

for(int a : l)

for(int b : r)

ans.push_back(f(a,b));

}

// Single number, e.g. s = "3"

if(ans.empty())

ans.push_back(std::stoi(input));

// memorize the answer for input

m_[input].swap(ans);

return m_[input];

}

unordered_map<string, vector<int>> m_;

};

Python3

# Author: Huahua, 44 ms

class Solution:

def diffWaysToCompute(self, input):

ops = {'+': lambda x, y: x + y,

'-': lambda x, y: x - y,

'*': lambda x, y: x * y}

def ways(s):

ans = []

for i in range(len(s)):

if s[i] in "+-*":

ans += [ops[s[i]](l, r) for l, r in itertools.product(ways(s[0:i]), ways(s[i+1:]))]

if not ans: ans.append(int(s))

return ans

return ways(input)

花花酱 LeetCode 21: Merge Two Sorted Lists

By zxi on September 3, 2017

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution 1: Iterative O(n)

// Author: Huahua

class Solution {

public:

Solution 1: Iterative

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail=&dummy;

while(l1 && l2) {

if(l1->val < l2->val) {

tail->next=l1;

l1=l1->next;

}else{

tail->next=l2;

l2=l2->next;

}

tail=tail->next;

}

if(l1) tail->next = l1;

if(l2) tail->next = l2;

return dummy.next;

}

};

Solution 2: Recursive O(n)

// Author: Huahua

class Solution {

public:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

// If one of the list is emptry, return the other one.

if(!l1 || !l2) return l1 ? l1 : l2;

// The smaller one becomes the head.

if(l1->val < l2->val) {

l1->next = mergeTwoLists(l1->next, l2);

return l1;

} else {

l2->next = mergeTwoLists(l1, l2->next);

return l2;

}

};

花花酱 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 241. Different Ways to Add Parentheses

C++

Python3

花花酱 LeetCode 110. Balanced Binary Tree

花花酱 Leetcode 140. Word Break II

Problem

Solution

Related Problems

花花酱 Leetcode 139. Word Break

Problem

Idea:

Solutions:

Huahua's Tech Road

花花酱 LeetCode 241. Different Ways to Add Parentheses

C++

Python3

花花酱 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: