Posts tagged as “string”

花花酱 LeetCode 925. Long Pressed Name

By zxi on October 20, 2018

Problem

Your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.

You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Example 1:

Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.

Example 2:

Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: 'e' must have been pressed twice, but it wasn't in the typed output.

Example 3:

Input: name = "leelee", typed = "lleeelee" 
Output: true

Example 4:

Input: name = "laiden", typed = "laiden"
Output: true
Explanation: It's not necessary to long press any character.

Note:

name.length <= 1000
typed.length <= 1000
The characters of name and typed are lowercase letters.

Solution: Two Pointers

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua, 0 ms

class Solution {

public:

bool isLongPressedName(string name, string typed) {

int i = 0;

int j = 0;

while (i < name.size() && j < typed.size()) {

if (name[i] == typed[j]) {

++i;

++j;

} else if (j > 0 && typed[j] == typed[j - 1]) {

++j;

} else {

return false;

}

while (j < typed.size() && typed[j] == typed[j - 1]) ++j;

return i == name.size() && j == typed.size();

}

};

C++ / Iterator

// Author: Huahua

class Solution {

public:

bool isLongPressedName(string name, string typed) {

auto it1 = begin(name);

auto it2 = begin(typed);

while (it1 != end(name) && it2 != end(typed)) {

if (*it1 == *it2) {

++it1;

++it2;

} else if (it2 != begin(typed) && *it2 == *prev(it2)) {

++it2;

} else {

return false;

}

while (it2 != end(typed) && *it2 == *prev(it2)) ++it2;

return it1 == end(name) && it2 == end(typed);

}

};

花花酱 LeetCode 921. Minimum Add to Make Parentheses Valid

By zxi on October 13, 2018

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

It is the empty string, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:

Input: "())"
Output: 1

Example 2:

Input: "((("
Output: 3

Example 3:

Input: "()"
Output: 0

Example 4:

Input: "()))(("
Output: 4

Note:

S.length <= 1000
S only consists of '(' and ')' characters.

Solution: Counting

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minAddToMakeValid(string S) {

int l = 0;

int m = 0;

for (char c : S) {

if (c == '(') ++l;

if (c == ')' && l > 0) {

--l;

++m;

}

return S.size() - m * 2;

}

};

花花酱 LeetCode 917. Reverse Only Letters

By zxi on October 6, 2018

Problem

Given a string S, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:

Input: "ab-cd"
Output: "dc-ba"

Example 2:

Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Note:

S.length <= 100
33 <= S[i].ASCIIcode <= 122
S doesn’t contain \ or "

Solution: Two Pointers

Time complexity: O(n)

Space complexity: O(1) – in place

C++/index

// Author: Huahua

class Solution {

public:

string reverseOnlyLetters(string S) {

int i = 0;

int j = S.length() - 1;

while (i < j) {

if (isalpha(S[i]) && isalpha(S[j])) {

swap(S[i++], S[j--]);

} else {

if (!isalpha(S[i])) ++i;

if (!isalpha(S[j])) --j;

}

return S;

}

};

C++/iter

// Author: Huahua

class Solution {

public:

string reverseOnlyLetters(string S) {

auto it1 = begin(S);

auto it2 = prev(end(S));

while (it1 < it2) {

if (isalpha(*it1) && isalpha(*it2)) {

swap(*it1++, *it2--);

} else {

if (!isalpha(*it1)) ++it1;

if (!isalpha(*it2)) --it2;

}

return S;

}

};

花花酱 LeetCode 28. Implement strStr()

By zxi on October 2, 2018

Problem

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Solution 1: Brute Force

Time complexity: O(mn)

Space complexity: O(1)

C++

// Author: Huahua, 4 ms

class Solution {

public:

int strStr(string haystack, string needle) {

const int l1 = haystack.length();

const int l2 = needle.length();

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

int j = 0;

while (j < l2 && haystack[i + j] == needle[j]) ++j;

if (j == l2) return i;

}

return -1;

}

};

Python3

# Author: Huahua

class Solution:

def strStr(self, haystack, needle):

l1 = len(haystack)

l2 = len(needle)

for i in range(l1 - l2 + 1):

if haystack[i:i+l2] == needle: return i

return -1

花花酱 LeetCode 14. Longest Common Prefix

By zxi on September 19, 2018

Problem

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Solution: Brute Force

Time complexity: O(mk), where k the length of common prefix.

Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

string longestCommonPrefix(vector<string>& strs) {

if (strs.empty()) return "";

string ans;

for (int i = 0; i < strs[0].size(); ++i) {

for (const string& s : strs)

if (s.length() <= i || s[i] != strs[0][i]) return ans;

ans += strs[0][i];

}

return ans;

}

};

Java

Time complexity: (mk + k^2)

// Author: Huahua

class Solution {

public String longestCommonPrefix(String[] strs) {

if (strs.length == 0) return "";

String ans = new String();

for (int i = 0; i < strs[0].length(); ++i) {

char c = strs[0].charAt(i);

for (String s : strs)

if (s.length() <= i || s.charAt(i) != c) return ans;

ans += c;

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def longestCommonPrefix(self, strs):

if not strs: return ""

ans = ""

for i in range(len(strs[0])):

for s in strs:

if len(s) <= i or s[i] != strs[0][i]: return ans

ans += strs[0][i]

return ans