Posts published in “String”

花花酱 LeetCode 1147. Longest Chunked Palindrome Decomposition

By zxi on August 4, 2019

Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:

Each a_i is a non-empty string;
Their concatenation a_1 + a_2 + ... + a_k is equal to text;
For all 1 <= i <= k, a_i = a_{k+1 - i}.

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

Solution: Greedy

Break the string when the shortest palindrome is found.
prefer to use string_view

Time complexity: O(n^2)
Space complexity: O(n)

C++

// Author: Huahua, 0 ms, 8.7 ms

class Solution {

public:

int longestDecomposition(string_view text) {

const int n = text.length();

if (n == 0) return 0;

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

if (text.substr(0, l) == text.substr(n - l))

return 2 + longestDecomposition(text.substr(l, n - 2 * l));

}

return 1;

}

};

花花酱 LeetCode 1108. Defanging an IP Address

By zxi on July 11, 2019

Given a valid (IPv4) IP address, return a defanged version of that IP address.

A defanged IP address replaces every period "." with "[.]".

Example 1:

Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"

Example 2:

Input: address = "255.100.50.0"
Output: "255[.]100[.]50[.]0"

Constraints:

The given address is a valid IPv4 address.

Solution: String

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

string defangIPaddr(string address) {

string output;

for (const char c : address) {

if (c == '.') output += "[.]";

else output += c;

}

return output;

}

};

花花酱 LeetCode 640. Solve the Equation

By zxi on May 10, 2019

Solve a given equation and return the value of x in the form of string “x=#value”. The equation contains only ‘+’, ‘-‘ operation, the variable x and its coefficient.

If there is no solution for the equation, return “No solution”.

If there are infinite solutions for the equation, return “Infinite solutions”.

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"

Solution: Parse the equation

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua, 0 ms, 8.5 MB

class Solution {

public:

string solveEquation(const string& equation) {

auto parse = [](string_view s) -> vector<int> {

int a{0}, b{0};

int sign = 1;

long t = 0;

bool d = false;

for (char c : s) {

if (isdigit(c)) {

d = true;

t = t * 10 + c - '0';

} else {

if (c == 'x')

a += (d ? t : 1) * sign;

else {

b += t * sign;

sign = c == '+' ? 1 : -1;

}

d = false;

t = 0;

}

b += t * sign;

return {a, b};

};

auto pos = equation.find('=');

auto l = parse(string_view(equation).substr(0, pos));

auto r = parse(string_view(equation).substr(pos + 1));

l[0] -= r[0];

l[1] -= r[1];

if (l[0] == 0)

return l[1] == 0 ? "Infinite solutions" : "No solution";

return "x=" + to_string(-l[1] / l[0]);

}

};

花花酱 LeetCode 831. Masking Personal Information

By zxi on April 24, 2019

We are given a personal information string S, which may represent either an email address or a phone number.

We would like to mask this personal information according to the following rules:

1. Email address:

We define a name to be a string of length ≥ 2 consisting of only lowercase letters a-z or uppercase letters A-Z.

An email address starts with a name, followed by the symbol '@', followed by a name, followed by the dot '.' and followed by a name.

All email addresses are guaranteed to be valid and in the format of "name1@name2.name3".

To mask an email, all names must be converted to lowercase and all letters between the first and last letter of the first name must be replaced by 5 asterisks '*'.

2. Phone number:

A phone number is a string consisting of only the digits 0-9 or the characters from the set {'+', '-', '(', ')', ' '}. You may assume a phone number contains 10 to 13 digits.

The last 10 digits make up the local number, while the digits before those make up the country code. Note that the country code is optional. We want to expose only the last 4 digits and mask all other digits.

The local number should be formatted and masked as "***-***-1111", where 1 represents the exposed digits.

To mask a phone number with country code like "+111 111 111 1111", we write it in the form "+***-***-***-1111". The '+' sign and the first '-' sign before the local number should only exist if there is a country code. For example, a 12 digit phone number mask should start with "+**-".

Note that extraneous characters like "(", ")", " ", as well as extra dashes or plus signs not part of the above formatting scheme should be removed.

Return the correct “mask” of the information provided.

Example 1:

Input: "LeetCode@LeetCode.com"
Output: "l*****e@leetcode.com"
Explanation: All names are converted to lowercase, and the letters between the
             first and last letter of the first name is replaced by 5 asterisks.
             Therefore, "leetcode" -> "l*****e".

Example 2:

Input: "AB@qq.com"
Output: "a*****b@qq.com"
Explanation: There must be 5 asterisks between the first and last letter 
             of the first name "ab". Therefore, "ab" -> "a*****b".

Example 3:

Input: "1(234)567-890"
Output: "***-***-7890"
Explanation: 10 digits in the phone number, which means all digits make up the local number.

Example 4:

Input: "86-(10)12345678"
Output: "+**-***-***-5678"
Explanation: 12 digits, 2 digits for country code and 10 digits for local number.

Notes:

S.length <= 40.
Emails have length at least 8.
Phone numbers have length at least 10.

Solution: String

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, running time: 4 ms, 8.4 MB

class Solution {

public:

string maskPII(string S) {

return isalpha(S[0]) ? maskEmail(S) : maskPhone(S);

}

private:

string maskEmail(const string& s) {

string email = s.substr(0, 1) + "*****" + s.substr(s.find('@') - 1);

transform(begin(email), end(email), begin(email), ::tolower);

return email;

}

string maskPhone(const string& s) {

string d;

for (char c : s) if (isdigit(c)) d += c;

string phone;

if (d.length() > 10)

phone += "+" + string(d.length() - 10, '*') + "-";

phone += "***-***-" + d.substr(d.length() - 4);

return phone;

}

};

花花酱 LeetCode 273. Integer to English Words

By zxi on April 3, 2019

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2³¹ – 1.

Example 1:

Input: 123
Output: "One Hundred Twenty Three"

Example 2:

Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Example 4:

Input: 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

Solution: Recursion

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

constexpr char * kUnder20[] = {"One", "Two", "Three", "Four", "Five",

"Six", "Seven", "Eight", "Nine","Ten",

"Eleven", "Twelve", "Thirteen", "Fourteen",

"Fifteen", "Sixteen", "Seventeen", "Eighteen",

"Nineteen"};

constexpr char * kUnder100[] = {"Twenty", "Thirty", "Forty", "Fifty",

"Sixty", "Seventy", "Eighty", "Ninety"};

constexpr char * kHTMB[] = {"Hundred", "Thousand", "Million", "Billion"};

constexpr long kP[] = {100, 1000, 1000*1000, 1000*1000*1000};

class Solution {

public:

string numberToWords(int n) {

if (n == 0) return "Zero";

return convert(n).substr(1);

}

private:

string convert(int n) {

if (n == 0) return "";

if (n < 20) return string(" ") + kUnder20[n - 1]; // 1 - 19

if (n < 100) return string(" ") + kUnder100[n / 10 - 2] + convert(n % 10); // 20 ~ 99

for (int i = 3; i >= 0; --i)

if (n >= kP[i]) return convert(n / kP[i]) + " " + kHTMB[i] + convert(n % kP[i]);

return "";

}

};