Posts published in “String”

花花酱 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)

花花酱 LeetCode 516. Longest Palindromic Subsequence

By zxi on May 28, 2018

Problem

题目大意：找出最长回文子序列的长度。

https://leetcode.com/problems/longest-palindromic-subsequence/description/

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"

Output:

One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:

"cbbd"

Output:

One possible longest palindromic subsequence is “bb”.

Solution: DP

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 102 ms

class Solution {

public:

int longestPalindromeSubseq(string s) {

const int n = s.length();

vector<vector<int>> dp(n, vector<int>(n, 0));

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

for (int i = 0; i <= n - l; ++i) {

int j = i + l - 1;

if (i == j) {

dp[i][j] = 1;

continue;

}

dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

if (s[i] == s[j])

dp[i][j] = dp[i + 1][j - 1] + 2;

}

return dp[0][n - 1];

}

};

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

int longestPalindromeSubseq(string s) {

const int n = s.length();

vector<int> dp0(n); // sols of len = l

vector<int> dp1(n); // sols of len = l - 1

vector<int> dp2(n); // sols of len = l - 2

for (int l = 1; l <= n; ++l) {

for (int i = 0; i <= n - l; ++i) {

int j = i + l - 1;

if (i == j) {

dp0[i] = 1;

continue;

}

if (s[i] == s[j])

dp0[i] = dp2[i + 1] + 2;

else

dp0[i] = max(dp1[i + 1], dp1[i]);

}

dp0.swap(dp1);

dp2.swap(dp0);

}

return dp1[0];

}

};

Python3

"""

Author: Huahua

Running time: 1276 ms

"""

class Solution:

def longestPalindromeSubseq(self, s):

n = len(s)

dp0 = [0] * n

dp1 = [1] * n

dp2 = [0] * n

for l in range(2, n + 1):

for i in range(0, n - l + 1):

j = i + l - 1

if s[i] == s[j]:

dp0[i] = dp2[i + 1] + 2

else:

dp0[i] = max(dp1[i + 1], dp1[i])

dp0, dp1, dp2 = dp2, dp0, dp1

return dp1[0]

// Author: Huahua

// Running time: 116 ms (beats 100%)

public class Solution {

public int LongestPalindromeSubseq(string s) {

var n = s.Length;

var dp0 = new int[n];

var dp1 = new int[n];

var dp2 = new int[n];

for (var l = 1; l <= n; ++l) {

for (var i = 0; i <= n - l; ++i) {

int j = i + l - 1;

if (i == j) {

dp0[i] = 1;

continue;

}

if (s[i] == s[j])

dp0[i] = dp2[i + 1] + 2;

else

dp0[i] = Math.Max(dp1[i], dp1[i + 1]);

}

var tmp = dp2;

dp2 = dp1;

dp1 = dp0;

dp0 = tmp;

}

return dp1[0];

}

花花酱 LeetCode 438. Find All Anagrams in a String

By zxi on May 28, 2018

Problem

题目大意：在s中找出所有p的Anagrams。

https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Solution: HashTable + Sliding Window

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

vector<int> findAnagrams(string s, string p) {

int n = s.length();

int l = p.length();

vector<int> ans;

vector<int> vp(26, 0);

vector<int> vs(26, 0);

for (char c : p) ++vp[c - 'a'];

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

if (i >= l) --vs[s[i - l] - 'a'];

++vs[s[i] - 'a'];

if (vs == vp) ans.push_back(i + 1 - l);

}

return ans;

}

};

花花酱 LeetCode 830. Positions of Large Groups

By zxi on May 13, 2018

Problem

In a string S of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like S = "abbxxxxzyy" has the groups "a", "bb", "xxxx", "z" and "yy".

Call a group large if it has 3 or more characters. We would like the starting and ending positions of every large group.

The final answer should be in lexicographic order.

Example 1:

Input: "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the single large group with starting 3 and ending positions 6.

Example 2:

Input: "abc"
Output: []
Explanation: We have "a","b" and "c" but no large group.

Example 3:

Input: "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]

Note: 1 <= S.length <= 1000

Solution: Brute Force

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

vector<vector<int>> largeGroupPositions(string S) {

constexpr int kLargeGroupSize = 3;

const int n = S.size();

vector<vector<int>> ans;

int c = 0;

for (int i = 0; i <= n; ++i, ++c) {

if (i == n || S[i] != S[i - 1]) {

if (c >= kLargeGroupSize) ans.push_back({i - c, i - 1});

c = 0;

}

return ans;

}

};

花花酱 LeetCode 824. Goat Latin

By zxi on April 29, 2018

Problem

A sentence S is given, composed of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to “Goat Latin” (a made-up language similar to Pig Latin.)

The rules of Goat Latin are as follows:

If a word begins with a vowel (a, e, i, o, or u), append "ma" to the end of the word.
For example, the word ‘apple’ becomes ‘applema’.
If a word begins with a consonant (i.e. not a vowel), remove the first letter and append it to the end, then add "ma".
For example, the word "goat" becomes "oatgma".
Add one letter 'a' to the end of each word per its word index in the sentence, starting with 1.
For example, the first word gets "a" added to the end, the second word gets "aa" added to the end and so on.

Return the final sentence representing the conversion from S to Goat Latin.

Example 1:

Input: "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Example 2:

Input: "The quick brown fox jumped over the lazy dog"
Output: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

Notes:

S contains only uppercase, lowercase and spaces. Exactly one space between each word.
1 <= S.length <= 100.

Solution: String

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string toGoatLatin(string S) {

const string vowls = "aeiouAEIOU";

string ans;

string word;

int index = 0;

istringstream s(S);

while (s >> word) {

if (vowls.find(word[0]) == string::npos)

word = word.substr(1) + word[0];

ans += " " + word + "ma" + string(++index, 'a');

}

return ans.substr(1);

}

};