Posts published in “String”

花花酱 LeetCode 228. Summary Ranges

By zxi on June 27, 2018

Problem

Given a sorted integer array without duplicates, return the summary of its ranges.

Example 1:

Input:  [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

Example 2:

Input:  [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.

Solution

Time complexity: O(n)

Space complexity: O(k)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

vector<string> summaryRanges(vector<int>& nums) {

int s = 0;

vector<string> ans;

for (size_t i = 1; i <= nums.size(); ++i) {

if (i == nums.size() || nums[i] != nums[i - 1] + 1) {

if (s == i - 1)

ans.push_back(to_string(nums[s]));

else

ans.push_back(to_string(nums[s]) + "->" + to_string(nums[i - 1]));

s = i;

}

return ans;

}

};

花花酱 LeetCode 856. Score of Parentheses

By zxi on June 26, 2018

Problem

Given a balanced parentheses string S, compute the score of the string based on the following rule:

() has score 1
AB has score A + B, where A and B are balanced parentheses strings.
(A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: "()"
Output: 1

Example 2:

Input: "(())"
Output: 2

Example 3:

Input: "()()"
Output: 2

Example 4:

Input: "(()(()))"
Output: 6

Solution1: Recursion

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 4ms

class Solution {

public:

int scoreOfParentheses(string S) {

return score(S, 0, S.length() - 1);

}

private:

int score(const string& S, int l, int r) {

if (r - l == 1) return 1; // "()"

int b = 0;

for (int i = l; i < r; ++i) {

if (S[i] == '(') ++b;

if (S[i] == ')') --b;

if (b == 0) // balanced

// score("(A)(B)") = score("(A)") + score("(B)")

return score(S, l, i) + score(S, i + 1, r);

}

// score("(A)") = 2 * score("A")

return 2 * score(S, l + 1, r - 1);

}

};

Solution2: Counting

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int scoreOfParentheses(string S) {

int ans = 0;

int d = -1;

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

d += S[i] == '(' ? 1 : -1;

if (S[i] == '(' && S[i + 1] == ')')

ans += 1 << d;

}

return ans;

}

};

花话酱 LeetCode 859. Buddy Strings

By zxi on June 26, 2018

Problem

Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.

Example 1:

Input: A = "ab", B = "ba"
Output: true

Example 2:

Input: A = "ab", B = "ab"
Output: false

Example 3:

Input: A = "aa", B = "aa"
Output: true

Example 4:

Input: A = "aaaaaaabc", B = "aaaaaaacb"
Output: true

Example 5:

Input: A = "", B = "aa"
Output: false

Note:

0 <= A.length <= 20000
0 <= B.length <= 20000
A and B consist only of lowercase letters.

Solution: HashTable

Time complexity: O(n)

Space complexity: O(26)

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

bool buddyStrings(string A, string B) {

if (A.length() != B.length()) return false;

vector<int> ca(26);

vector<int> cb(26);

int diff = 0;

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

if (A[i] != B[i] && diff++ > 2) return false;

++ca[A[i]-'a'];

++cb[B[i]-'a'];

}

for (int i = 0; i < 26; ++i) {

if (diff == 0 && ca[i] > 1) return true;

if (ca[i] != cb[i]) return false;

}

return diff == 2;

}

};

花花酱 LeetCode 848. Shifting Letters

By zxi on June 11, 2018

Problem

We have a string S of lowercase letters, and an integer array shifts.

Call the shift of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a').

For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'.

Now for each shifts[i] = x, we want to shift the first i+1 letters of S, x times.

Return the final string after all such shifts to S are applied.

Example 1:

Input: S = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: 
We start with "abc".
After shifting the first 1 letters of S by 3, we have "dbc".
After shifting the first 2 letters of S by 5, we have "igc".
After shifting the first 3 letters of S by 9, we have "rpl", the answer.

Note:

1 <= S.length = shifts.length <= 20000
0 <= shifts[i] <= 10 ^ 9

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 54 ms

class Solution {

public:

string shiftingLetters(string S, vector<int>& shifts) {

int c = 0;

for (int i = shifts.size() - 1; i >= 0; --i) {

c += (shifts[i] % 26);

S[i] = (S[i] - 'a' + c) % 26 + 'a';

}

return S;

}

};

花花酱 LeetCode 844. Backspace String Compare

By zxi on June 3, 2018

Problem

题目大意：给你2个字符串表示打字顺序，判断它们的结果是否相同，’#’表示退格键。

https://leetcode.com/problems/backspace-string-compare/description/

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.

Solution: Simulation

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

Space complexity: O(|S| + |T|)

C++

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

bool backspaceCompare(string S, string T) {

return type(S) == type(T);

}

private:

string type(string S) {

string o;

for (char c : S)

if (c == '#') {

if (!o.empty())

o.pop_back();

} else {

o.push_back(c);

}

return o;

}

};

Java

// Author: Huahua, 7 ms

class Solution {

public boolean backspaceCompare(String S, String T) {

return type(S).equals(type(T));

}

private String type(String s) {

StringBuilder sb = new StringBuilder();

for (char c : s.toCharArray()) {

if (c == '#') {

if (sb.length() > 0)

sb.setLength(sb.length() - 1);

} else {

sb.append(c);

}

return sb.toString();

}

Python3

# Author: Huahua, 40 ms

class Solution:

def backspaceCompare(self, S, T):

def sim(S):

ans = ''

for c in S:

if c == '#':

if len(ans) > 0: ans = ans[:-1]

else:

ans += c

return ans

return sim(S) == sim(T)