Posts published in “String”

花花酱 LeetCode 567. Permutation in String

By zxi on June 28, 2018

Problem

题目大意：给你s1, s2，问你s2的子串中是否存在s1的一个排列。

https://leetcode.com/problems/permutation-in-string/description/

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

Solution: Sliding Window

Time Complexity: O(l1 + l2 * 26) = O(l1 + l2)

Space Complexity: O(26 * 2) = O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

bool checkInclusion(string s1, string s2) {

int l1 = s1.length();

int l2 = s2.length();

vector<int> c1(26);

vector<int> c2(26);

for (const char c : s1)

++c1[c - 'a'];

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

if (i >= l1)

--c2[s2[i - l1] - 'a'];

++c2[s2[i] - 'a'];

if (c1 == c2) return true;

}

return false;

}

};

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;

}

};

Posts published in “String”

花花酱 LeetCode 567. Permutation in String

Problem

Solution: Sliding Window

Related Problems

花花酱 LeetCode 228. Summary Ranges

Problem

Solution

花花酱 LeetCode 856. Score of Parentheses

Problem

Solution1: Recursion

Solution2: Counting

花话酱 LeetCode 859. Buddy Strings

Problem

Solution: HashTable

花花酱 LeetCode 848. Shifting Letters

Problem

Solution