Posts tagged as “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 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);

}

};

花花酱 LeetCode 820. Short Encoding of Words

By zxi on April 24, 2018

Problem

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

Input: words = ["time", "me", "bell"] Output: 10 Explanation: S = "time#bell#" and indexes = [0, 2, 5].

Note:

1 <= words.length <= 2000.
1 <= words[i].length <= 7.
Each word has only lowercase letters.

Idea

Remove all the words that are suffix of other words.

Solution

Time complexity: O(n*l^2)

Space complexity: O(n*l)

// Author: Huahua

// Running time: 43 ms

class Solution {

public:

int minimumLengthEncoding(vector<string>& words) {

unordered_set<string> s(words.begin(), words.end());

for (const string& w : words) {

for (int i = w.length() - 1; i > 0; --i)

s.erase(w.substr(i));

}

int ans = 0;

for (const string& w : s)

ans += w.length() + 1;

return ans;

}

};