Huahua’s Tech Road

花花酱 LeetCode 87. Scramble String

By zxi on March 14, 2020

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

Solution: Recursion

isScramble(s1, s2)
if s1 == s2: return true
if sorted(s1) != sroted(s2): return false
We try all possible partitions:

s1[0:l] v.s s2[0:l] && s1[l:] vs s2[l:]
s1[0:l] vs s2[L-l:l] && s1[l:] vs s2[0:L-l]

Time complexity: O(n^5)
Space complexity: O(n^4)

C++

class Solution {

public:

bool isScramble(string_view s1, string_view s2) {

const int l = s1.length();

if (s1 == s2) return true;

if (freq(s1) != freq(s2)) return false;

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

if (isScramble(s1.substr(0, i), s2.substr(0, i))

&& isScramble(s1.substr(i), s2.substr(i))

|| isScramble(s1.substr(0, i), s2.substr(l - i, i))

&& isScramble(s1.substr(i), s2.substr(0, l - i)))

return true;

return false;

}

private:

vector<int> freq(string_view s) {

vector<int> f(26);

for (char c : s) ++f[c - 'a'];

return f;

}

};

Python3

# Author: Huahua

class Solution:

@lru_cache(maxsize=None) # optional

def isScramble(self, s1: str, s2: str) -> bool:

if s1 == s2: return True

# important, TLE if commneted out

if Counter(s1) != Counter(s2): return False

L = len(s1)

for l in range(1, L):

if self.isScramble(s1[0:l], s2[0:l]) and self.isScramble(s1[l:], s2[l:]):

return True

if self.isScramble(s1[0:l], s2[L-l:]) and self.isScramble(s1[l:], s2[0:L-l]):

return True

return False

花花酱 LeetCode 306. Additive Number

By zxi on March 14, 2020

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"
Output: true
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199. 
             1 + 99 = 100, 99 + 100 = 199

Constraints:

num consists only of digits '0'-'9'.
1 <= num.length <= 35

Solution: DFS

Time complexity: O(n^2)
Space complexity: O(n)

C++

using SV = std::string_view;

class Solution {

public:

bool isAdditiveNumber(SV s) {

auto add = [](SV s1, SV s2) {

const int l1 = s1.length(), l2 = s2.length();

string s3(max(l1, l2) + 1, '0');

for (int i = 0; i < s3.size() - 1; ++i) {

int n1 = i < l1 ? s1[l1 - i - 1] - '0' : 0;

int n2 = i < l2 ? s2[l2 - i - 1] - '0' : 0;

s3[i] += n1 + n2;

if (s3[i] > '9') {

s3[i] -= 10;

++s3[i + 1];

}

while (s3.back() == '0' && s3.length() > 1) s3.pop_back();

return string{rbegin(s3), rend(s3)};

};

auto isValid = [](SV s) { return s.length() == 1 || s[0] != '0'; };

function<bool(SV, SV, SV)> additive = [&](SV s1, SV s2, SV right) {

if (!isValid(s1) || !isValid(s2)) return false;

string s3 = add(s1, s2);

const int l3 = s3.length();

if (right.substr(0, l3) != s3) return false;

if (right.length() == l3) return true;

return additive(s2, s3, right.substr(l3));

};

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

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

if (additive(s.substr(0, i), s.substr(i, j), s.substr(i + j)))

return true;

return false;

}

};

Python3

class Solution:

def isAdditiveNumber(self, num: str) -> bool:

n = len(num)

def valid(s): return len(s) == 1 or s[0] != '0'

def additive(s1, s2, right):

if not valid(s1) or not valid(s2): return False

s3 = str(int(s1) + int(s2))

if right.startswith(s3):

if right == s3: return True

return additive(s2, s3, right[len(s3):])

return False

for l1 in range(1, n // 2 + 1):

for l2 in range(1, n + 1 - l1):

if additive(num[:l1], num[l1:l1+l2], num[l1+l2:]):

return True

return False

花花酱 LeetCode 240. Search a 2D Matrix II

By zxi on March 13, 2020

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Solution 1: Two Pointers

Start from first row + last column, if the current value is larger than target, –column; if smaller then ++row.

e.g.
1. r = 0, c = 4, v = 15, 15 > 5 => –c
2. r = 0, c = 3, v = 11, 11 > 5 => –c
3. r = 0, c = 2, v = 7, 7 > 5 => –c
4. r = 0, c = 1, v = 4, 4 < 5 => ++r
5. r = 1, c = 1, v = 5, 5 = 5, found it!

Time complexity: O(m + n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool searchMatrix(vector<vector<int>>& matrix, int target) {

if (matrix.empty() || matrix[0].empty()) return false;

const int m = matrix.size();

const int n = matrix[0].size();

int r = 0;

int c = matrix[0].size() - 1;

while (r < m && c >= 0) {

if (matrix[r][c] == target) return true;

else if (matrix[r][c] > target) --c;

else ++r;

}

return false;

}

};

花花酱 LeetCode 229. Majority Element II

By zxi on March 13, 2020

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

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

Solution: Boyer–Moore Voting Algorithm

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

C++

// Author: Huahua

class Solution {

public:

vector<int> majorityElement(vector<int>& nums) {

int n1 = 0;

int c1 = 0;

int n2 = 1;

int c2 = 0;

for (int num : nums) {

if (num == n1) {

++c1;

} else if (num == n2) {

++c2;

} else if (c1 == 0) {

n1 = num;

c1 = 1;

} else if (c2 == 0) {

n2 = num;

c2 = 1;

} else {

--c1;

--c2;

}

c1 = c2 = 0;

for (int num : nums) {

if (num == n1) ++c1;

else if (num == n2) ++c2;

}

const int c = nums.size() / 3;

vector<int> ans;

if (c1 > c) ans.push_back(n1);

if (c2 > c) ans.push_back(n2);

return ans;

}

};

Python3

# Author: Huahua

class Solution:

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

n1, c1, n2, c2 = 0, 0, 1, 0

for num in nums:

if num == n1: c1 += 1

elif num == n2: c2 += 1

elif c1 == 0: n1, c1 = num, 1

elif c2 == 0: n2, c2 = num, 1

else: c1, c2 = c1 - 1, c2 -1

c1, c2 = 0, 0

for num in nums:

if num == n1: c1 += 1

elif num == n2: c2 += 1

ans = []

if c1 > len(nums) // 3: ans.append(n1)

if c2 > len(nums) // 3: ans.append(n2)

return ans

花花酱 LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

By zxi on March 13, 2020

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Follow up: Solve the problem if repeated values on the tree are allowed.

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:

Input: tree = [7], target =  7
Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Example 4:

Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5

Example 5:

Input: tree = [1,2,null,3], target = 2
Output: 2

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
The values of the nodes of the tree are unique.
target node is a node from the original tree and is not null.

Solution: Recursion

Traverse both trees in the same order, if original == target, return cloned.

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {

if (!original) return nullptr;

if (original == target) return cloned;

auto l = getTargetCopy(original->left, cloned->left, target);

auto r = getTargetCopy(original->right, cloned->right, target);

return l ? l : r;

}

};

Python3

# Author: Huahua

class Solution:

def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

if not original: return None

if original == target: return cloned

return self.getTargetCopy(original.left, cloned.left, target) or \

self.getTargetCopy(original.right, cloned.right, target)

Huahua's Tech Road

花花酱 LeetCode 87. Scramble String

Solution: Recursion

C++

Python3

花花酱 LeetCode 306. Additive Number

Solution: DFS

C++

Python3

花花酱 LeetCode 240. Search a 2D Matrix II

Solution 1: Two Pointers

C++

花花酱 LeetCode 229. Majority Element II

Solution: Boyer–Moore Voting Algorithm

C++

Python3

Related Problem

花花酱 LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Solution: Recursion

C++

Python3