Posts tagged as “recursion”

花花酱 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 139. Word Break

By zxi on September 2, 2017

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 486. Predict the Winner

By zxi on March 24, 2017

Problem

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.

Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
1 <= length of the array <= 20.
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.

Solution 1: Recursion

Time complexity: O(2^n)

Space complexity: O(n)

// Author: Huahua

// Running time: 67 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

return getScore(nums, 0, nums.size() - 1) >= 0;

}

private:

// Max diff (my_score - op_score) of subarray nums[l] ~ nums[r].

int getScore(vector<int>& nums, int l, int r) {

if (l == r) return nums[l];

return max(nums[l] - getScore(nums, l + 1, r),

nums[r] - getScore(nums, l, r - 1));

}

};

Solution 2: Recursion + Memoization

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

m_ = vector<vector<int>>(nums.size(), vector<int>(nums.size(), INT_MIN));

return getScore(nums, 0, nums.size() - 1) >= 0;

}

private:

vector<vector<int>> m_;

// Max diff (my_score - op_score) of subarray nums[l] ~ nums[r].

int getScore(vector<int>& nums, int l, int r) {

if (l == r) return nums[l];

if (m_[l][r] != INT_MIN) return m_[l][r];

m_[l][r] = max(nums[l] - getScore(nums, l + 1, r),

nums[r] - getScore(nums, l, r - 1));

return m_[l][r];

}

};

DP version

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

const int n = nums.size();

vector<vector<int>> dp(n, vector<int>(n, INT_MIN));

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

dp[i][i] = nums[i];

for (int l = 2; l <= n; ++l)

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

int j = i + l - 1;

dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);

}

return dp[0][n - 1] >= 0;

}

};

Posts tagged as “recursion”

花花酱 LeetCode 241. Different Ways to Add Parentheses

C++

Python3

花花酱 LeetCode 21: Merge Two Sorted Lists

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

花花酱 LeetCode 486. Predict the Winner

Problem

Solution 1: Recursion

Solution 2: Recursion + Memoization

Related Problem