Posts tagged as “string”

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

花花酱 LeetCode 13. Roman to Integer

By zxi on September 19, 2018

Problem

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: C = 100, L = 50, XXX = 30 and III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Solution

accumulate the value of each letter.

If the value of current letter is greater than the previous one, deduct twice of the previous value.

e.g. IX, 1 + 10 – 2 * 1 = 9 instead of 1 + 10 = 11

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int romanToInt(string s) {

map<char, int> m{{'I', 1}, {'V', 5},

{'X', 10}, {'L', 50},

{'C', 100}, {'D', 500},

{'M', 1000}};

int ans = 0;

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

ans += m[s[i]];

if (i > 0 && m[s[i]] > m[s[i - 1]])

ans -= 2 * m[s[i - 1]];

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

private int v(char R) {

switch (R) {

case 'I' : return 1;

case 'V' : return 5;

case 'X' : return 10;

case 'L' : return 50;

case 'C' : return 100;

case 'D' : return 500;

case 'M' : return 1000;

default: break;

}

return 0;

}

public int romanToInt(String s) {

int ans = 0;

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

ans += v(s.charAt(i));

if ( i > 0 && v(s.charAt(i)) > v(s.charAt(i - 1)))

ans -= 2 * v(s.charAt(i - 1));

}

return ans;

}

Python3

class Solution:

def romanToInt(self, s):

m = {'I' : 1, 'V': 5, 'X': 10, 'L' : 50,

'C' : 100, 'D': 500, 'M': 1000}

ans = m[s[0]]

for c, p in zip(s[1:], s[0:-1]):

ans += m[c]

if m[c] > m[p]: ans -= 2 * m[p]

return ans