Posts published in “String”

花花酱 LeetCode 214. Shortest Palindrome

By zxi on February 20, 2018

题目大意：给你一个字符串你可以在它的前面添加一些字符，返回最短的回文字符串。

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(n)

C++ w/ copy

// Author: Huahua

// Running time: 102 ms (<25.74%)

class Solution {

public:

string shortestPalindrome(string s) {

const string r(s.rbegin(), s.rend());

const int n = s.size();

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

if (s.substr(0, n - i) == r.substr(i))

return r.substr(0, i) + s;

return "";

}

};

C++ w/o copy

// Author: Huahua

// Running time: 13 ms (<49.74%)

class Solution {

public:

string shortestPalindrome(string s) {

const string r(s.rbegin(), s.rend());

const int n = s.size();

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

if (s.compare(0, n - i, r, i, n - i) == 0)

return r.substr(0, i) + s;

return "";

}

};

花花酱 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 636. Exclusive Time of Functions

By zxi on February 5, 2018

题目大意：给你一些函数的起始/终止时间的日志，让你输出每个函数的总运行时间。假设单核单线程，支持递归函数。

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.

A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.

Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id.

Example 1:

Input:

n = 2

logs =

["0:start:0",

"1:start:2",

"1:end:5",

"0:end:6"]

Output:[3, 4]

Explanation:

Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.

Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.

Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.

So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

Note:

Input logs will be sorted by timestamp, NOT log id.
Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
Two functions won’t start or end at the same time.
Functions could be called recursively, and will always end.
1 <= n <= 100

Solution: Simulate using stack

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

vector<int> exclusiveTime(int n, vector<string>& logs) {

vector<int> ans(n, 0);

char action[6];

int fid;

int curr;

int prev;

stack<int> s;

for (const string& log : logs) {

sscanf(log.c_str(), "%d:%[a-z]:%d", &fid, action, &curr);

if (action[0] == 's') {

if (!s.empty())

ans[s.top()] += curr - prev;

s.push(fid);

prev = curr;

} else {

ans[s.top()] += curr - prev + 1;

s.pop();

prev = curr + 1;

}

return ans;

}

};

花花酱 LeetCode 771. Jewels and Stones

By zxi on February 2, 2018

题目大意：给你宝石的类型，再给你一堆石头，返回里面宝石的数量。

Problem:

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

S and J will consist of letters and have length at most 50.
The characters in J are distinct.

Solution 1: HashTable

Time complexity: O(|J| + |S|)

Space complexity: O(128) / O(|J|)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int numJewelsInStones(string J, string S) {

std::vector<int> f(128, 0);

int ans = 0;

for (const char j : J)

f[j] = 1;

for (const char s : S)

ans += f[s] & 1;

return ans;

}

};

C++ v2

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

int numJewelsInStones(const string& J, const string& S) {

std::set<char> f(J.begin(), J.end());

return std::count_if(S.begin(), S.end(),

[&f](const char c) { return f.count(c); });

}

};

Java

// Author: Huahua

// Running time: 18 ms

class Solution {

public int numJewelsInStones(String J, String S) {

int[] f = new int[128];

for (final char c : J.toCharArray())

f[c] = 1;

int ans = 0;

for (final char c : S.toCharArray())

ans += f[c];

return ans;

}

Python

"""

Author: Huahua

Running time: 43 ms

"""

class Solution(object):

def numJewelsInStones(self, J, S):

f = set(J)

return sum([s in f for s in S])

花花酱 LeetCode 282. Expression Add Operators

By zxi on January 30, 2018

题目大意：给你一个字符串，让你在数字之间加上+,-,*使得等式的值等于target。让你输出所有满足条件的表达式。

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"]

"232", 8 -> ["2*3+2", "2+3*2"]

"105", 5 -> ["1*0+5","10-5"]

"00", 0 -> ["0+0", "0-0", "0*0"]

"3456237490", 9191 -> []

Slides:

Solution 1: DFS

Time complexity: O(4^n)

Space complexity: O(n^2) -> O(n)

C++

// Author: Huahua

// Running time: 128 ms (<79.97%)

class Solution {

public:

vector<string> addOperators(string num, int target) {

vector<string> ans;

dfs(num, target, 0, "", 0, 0, &ans);

return ans;

}

private:

void dfs(const string& num, const int target, // input

int pos, const string& exp, long prev, long curr, // state

vector<string>* ans) { // output

if (pos == num.length()) {

if (curr == target) ans->push_back(exp);

return;

}

for (int l = 1; l <= num.size() - pos; ++l) {

string t = num.substr(pos, l);

if (t[0] == '0' && t.length() > 1) break; // 0X...

long n = std::stol(t);

if (n > INT_MAX) break;

if (pos == 0) {

dfs(num, target, l, t, n, n, ans);

continue;

}

dfs(num, target, pos + l, exp + '+' + t, n, curr + n, ans);

dfs(num, target, pos + l, exp + '-' + t, -n, curr - n, ans);

dfs(num, target, pos + l, exp + '*' + t, prev * n, curr - prev + prev * n, ans);

}

};

C++ / SC O(n)

// Author: Huahua

// Running time: 13 ms (< 99.14%)

class Solution {

public:

vector<string> addOperators(string num, int target) {

vector<string> ans;

string exp(num.length() * 2, '\0');

dfs(num, target, 0, exp, 0, 0, 0, &ans);

return ans;

}

private:

void dfs(const string& num, const int target,

int pos, string& exp, int len, long prev, long curr,

vector<string>* ans) {

if (pos == num.length()) {

if (curr == target) ans->push_back(exp.substr(0, len));

return;

}

long n = 0;

int s = pos;

int l = len;

if (s != 0) ++len;

while (pos < num.size()) {

n = n * 10 + (num[pos] - '0');

if (num[s] == '0' && pos - s > 0) break; // 0X... invalid number

if (n > INT_MAX) break; // too long

exp[len++] = num[pos++];

if (s == 0) {

dfs(num, target, pos, exp, len, n, n, ans);

continue;

}

exp[l] = '+'; dfs(num, target, pos, exp, len, n, curr + n, ans);

exp[l] = '-'; dfs(num, target, pos, exp, len, -n, curr - n, ans);

exp[l] = '*'; dfs(num, target, pos, exp, len, prev * n, curr - prev + prev * n, ans);

}

};

Java

// Author: Huahua

// Running time: 16 ms (<99.17%)

class Solution {

private List<String> ans;

private char[] num;

private char[] exp;

private int target;

public List<String> addOperators(String num, int target) {

this.num = num.toCharArray();

this.ans = new ArrayList<>();

this.target = target;

this.exp = new char[num.length() * 2];

dfs(0, 0, 0, 0);

return ans;

}

private void dfs(int pos, int len, long prev, long curr) {

if (pos == num.length) {

if (curr == target)

ans.add(new String(exp, 0, len));

return;

}

int s = pos;

int l = len;

if (s != 0) ++len;

long n = 0;

while (pos < num.length) {

if (num[s] == '0' && pos - s > 0) break; // 0X...

n = n * 10 + (int)(num[pos] - '0');

if (n > Integer.MAX_VALUE) break; // too long

exp[len++] = num[pos++]; // copy exp

if (s == 0) {

dfs(pos, len, n, n);

continue;

}

exp[l] = '+'; dfs(pos, len, n, curr + n);

exp[l] = '-'; dfs(pos, len, -n, curr - n);

exp[l] = '*'; dfs(pos, len, prev * n, curr - prev + prev * n);

}