花花酱 LeetCode 784. Letter Case Permutation

By zxi on February 20, 2018

题目大意：给你一个字符串，每个字母可以变成大写也可以变成小写。让你输出所有可能字符串。

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:

Input: S = "a1b2"

Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"

Output: ["3z4", "3Z4"]

Input: S = "12345"

Output: ["12345"]

Note:

S will be a string with length at most 12.
S will consist only of letters or digits.

Solution 1: DFS

Time complexity: O(n*2^l), l = # of letters in the string

Space complexity: O(n) + O(n*2^l)

C++

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

vector<string> letterCasePermutation(string S) {

vector<string> ans;

dfs(S, 0, ans);

return ans;

}

private:

void dfs(string& S, int s, vector<string>& ans) {

if (s == S.length()) {

ans.push_back(S);

return;

}

dfs(S, s + 1, ans);

if (!isalpha(S[s])) return;

S[s] ^= (1 << 5);

dfs(S, s + 1, ans);

S[s] ^= (1 << 5);

}

};

Java

// Author: Huahua

// Running time: 8 ms

class Solution {

public List<String> letterCasePermutation(String S) {

List<String> ans = new ArrayList<>();

dfs(S.toCharArray(), 0, ans);

return ans;

}

private void dfs(char[] S, int i, List<String> ans) {

if (i == S.length) {

ans.add(new String(S));

return;

}

dfs(S, i + 1, ans);

if (!Character.isLetter(S[i])) return;

S[i] ^= 1 << 5;

dfs(S, i + 1, ans);

S[i] ^= 1 << 5;

}

Python 3

"""

Author: Huahua

Running time: 92 ms

"""

class Solution:

def letterCasePermutation(self, S):

ans = []

def dfs(S, i, n):

if i == n:

ans.append(''.join(S))

return

dfs(S, i + 1, n)

if not S[i].isalpha(): return

S[i] = chr(ord(S[i]) ^ (1<<5))

dfs(S, i + 1, n)

S[i] = chr(ord(S[i]) ^ (1<<5))

dfs(list(S), 0, len(S))

return ans

花花酱 LeetCode 769. Max Chunks To Make Sorted

By zxi on February 2, 2018

题目大意：给你一个0 ~ n-1的排列，问你最多能分成几组，每组分别排序后能够组成0 ~ n-1。

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [4,3,2,1,0]

Output: 1

Explanation:

Splitting into two or more chunks will not return the required result.

For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

Input: arr = [1,0,2,3,4]

Output: 4

Explanation:

We can split into two chunks, such as [1, 0], [2, 3, 4].

However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

Note:

arr will have length in range [1, 10].
arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

Solution 1: Max so far / Set

Time complexity: O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

int ans = 0;

set<int> s;

for (int i = 0; i < arr.size(); ++i) {

s.insert(arr[i]);

if (*s.rbegin() == i) ++ans;

}

return ans;

}

};

Solution 2: Max so far

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

int ans = 0;

int m = 0;

for (int i = 0; i < arr.size(); ++i) {

m = max(m, arr[i]);

if (m == i) ++ans;

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 5 ms

class Solution {

public int maxChunksToSorted(int[] arr) {

int max = 0;

int ans = 0;

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

max = Math.max(max, arr[i]);

if (max == i) ++ans;

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 53 ms

"""

class Solution:

def maxChunksToSorted(self, arr):

m = 0

ans = 0

for i, n in enumerate(arr):

if n > m: m = n

if m == i: ans += 1

return ans

花花酱 LeetCode 39. Combination Sum

By zxi on October 3, 2017

Problem:

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[

[7],

[2, 2, 3]

]

Idea:

DFS

Solution: C++

class Solution {

public:

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

vector<vector<int>> ans;

vector<int> cur;

std::sort(candidates.begin(), candidates.end());

dfs(candidates, target, 0, cur, ans);

return ans;

}

private:

void dfs(vector<int>& candidates, int target, int s, vector<int>& cur, vector<vector<int>>& ans) {

if (target == 0) {

ans.push_back(cur);

return;

}

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

if (candidates[i] > target) break;

cur.push_back(candidates[i]);

dfs(candidates, target - candidates[i], i, cur, ans);

cur.pop_back();

}

};

Python

"""

Author: Huahua

Runtime: 75 ms (batter than 97.04%)

"""

class Solution(object):

def combinationSum(self, candidates, target):

def dfs(candidates, target, s, curr, ans):

if target == 0:

ans.append(curr[:])

return

for i in xrange(s, len(candidates)):

if candidates[i] > target: return

curr.append(candidates[i])

dfs(candidates, target - candidates[i], i, curr, ans)

curr.pop()

ans = []

candidates.sort()

dfs(candidates, target, 0, [], ans);

return ans

Posts tagged as “permutation”

花花酱 LeetCode 784. Letter Case Permutation

Solution 1: DFS

C++

Java

Python 3

花花酱 LeetCode 769. Max Chunks To Make Sorted

花花酱 LeetCode 39. Combination Sum