Posts tagged as “string”

花花酱 LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One

By zxi on April 5, 2020

Given a number s in their binary representation. Return the number of steps to reduce it to 1 under the following rules:

If the current number is even, you have to divide it by 2.
If the current number is odd, you have to add 1 to it.

It’s guaranteed that you can always reach to one for all testcases.

Example 1:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.

Example 2:

Input: s = "10"
Output: 1
Explanation: "10" corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.

Example 3:

Input: s = "1"
Output: 0

Constraints:

1 <= s.length <= 500
s consists of characters ‘0’ or ‘1’
s[0] == '1'

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int numSteps(string s) {

int ans = 0;

int carry = 0;

// The highest bit must be 1,

// process to the 2nd highest bit

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

if (s[i] - '0' + carry == 1) {

ans += 2; // odd: +1, even: / 2

carry = 1; // always has a carry

} else {

ans += 1; // even: / 2

// carray remains e.g. 1 + 1 = 10, or 0 + 0 = 00

}

// If there is a carry, then it's even, one more step.

return ans + carry;

}

};

Python3

# Author: Huahua

class Solution:

def numSteps(self, s: str) -> int:

ans, carry = 0, 0

for i in range(1, len(s)):

if ord(s[-i]) - ord('0') + carry == 1:

ans += 2

carry = 1

else:

ans += 1

return ans + carry

花花酱 LeetCode 1392. Longest Happy Prefix

By zxi on March 21, 2020

A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).

Given a string s. Return the longest happy prefix of s .

Return an empty string if no such prefix exists.

Example 1:

Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".

Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.

Example 3:

Input: s = "leetcodeleet"
Output: "leet"

Example 4:

Input: s = "a"
Output: ""

Constraints:

1 <= s.length <= 10^5
s contains only lowercase English letters.

Solution: Rolling Hash

Time complexity: O(n) / worst case: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string longestPrefix(string_view s) {

const int kMod = 16769023;

const int kBase = 128;

const int n = s.length();

int p = 0;

int q = 0;

int a = 1;

int ans = 0;

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

p = (p + a * s[i - 1]) % kMod;

q = (q * kBase + s[n - i]) % kMod;

a = (a * kBase) % kMod;

if (p == q && s.substr(0, i) == s.substr(n - i))

ans = i;

}

return string(s.substr(0, ans));

}

};

花花酱 LeetCode 306. Additive Number

By zxi on March 14, 2020

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"
Output: true
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199. 
             1 + 99 = 100, 99 + 100 = 199

Constraints:

num consists only of digits '0'-'9'.
1 <= num.length <= 35

Solution: DFS

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

C++

using SV = std::string_view;

class Solution {

public:

bool isAdditiveNumber(SV s) {

auto add = [](SV s1, SV s2) {

const int l1 = s1.length(), l2 = s2.length();

string s3(max(l1, l2) + 1, '0');

for (int i = 0; i < s3.size() - 1; ++i) {

int n1 = i < l1 ? s1[l1 - i - 1] - '0' : 0;

int n2 = i < l2 ? s2[l2 - i - 1] - '0' : 0;

s3[i] += n1 + n2;

if (s3[i] > '9') {

s3[i] -= 10;

++s3[i + 1];

}

while (s3.back() == '0' && s3.length() > 1) s3.pop_back();

return string{rbegin(s3), rend(s3)};

};

auto isValid = [](SV s) { return s.length() == 1 || s[0] != '0'; };

function<bool(SV, SV, SV)> additive = [&](SV s1, SV s2, SV right) {

if (!isValid(s1) || !isValid(s2)) return false;

string s3 = add(s1, s2);

const int l3 = s3.length();

if (right.substr(0, l3) != s3) return false;

if (right.length() == l3) return true;

return additive(s2, s3, right.substr(l3));

};

for (int i = 1; i <= s.size(); ++i)

for (int j = 1; i + j <= s.size(); ++j)

if (additive(s.substr(0, i), s.substr(i, j), s.substr(i + j)))

return true;

return false;

}

};

Python3

class Solution:

def isAdditiveNumber(self, num: str) -> bool:

n = len(num)

def valid(s): return len(s) == 1 or s[0] != '0'

def additive(s1, s2, right):

if not valid(s1) or not valid(s2): return False

s3 = str(int(s1) + int(s2))

if right.startswith(s3):

if right == s3: return True

return additive(s2, s3, right[len(s3):])

return False

for l1 in range(1, n // 2 + 1):

for l2 in range(1, n + 1 - l1):

if additive(num[:l1], num[l1:l1+l2], num[l1+l2:]):

return True

return False

花花酱 LeetCode 165. Compare Version Numbers

By zxi on March 9, 2020

Compare two version numbers version1 and version2.
If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.

The . character does not represent a decimal point and is used to separate number sequences.

For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.

Example 1:

Input: version1 = "0.1", version2 = "1.1"
Output: -1

Example 2:

Input: version1 = "1.0.1", version2 = "1"
Output: 1

Example 3:

Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1

Example 4:

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both “01” and “001" represent the same number “1”

Example 5:

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: The first version number does not have a third level revision number, which means its third level revision number is default to "0"

Note:

Version strings are composed of numeric strings separated by dots . and this numeric strings may have leading zeroes.
Version strings do not start or end with dots, and they will not be two consecutive dots.

Solution: String

Split the version string to a list of numbers, and compare two lists.

Time complexity: O(l1 + l2)
Space complexity: O(l1 + l2)

C++

// Author: Huahua

class Solution {

public:

int compareVersion(string version1, string version2) {

const auto& v1 = parseVersion(version1);

const auto& v2 = parseVersion(version2);

int i1 = 0, i2 = 0;

while (i1 < v1.size() || i2 < v2.size()) {

int n1 = i1 < v1.size() ? v1[i1++] : 0;

int n2 = i2 < v2.size() ? v2[i2++] : 0;

if (n1 < n2) return -1;

else if (n1 > n2) return 1;

}

return 0;

}

private:

vector<int> parseVersion(const string& version) {

vector<int> v;

int s = 0;

for (char c : version) {

if (c == '.') {

v.push_back(s);

s = 0;

} else {

s = s * 10 + (c - '0');

}

v.push_back(s);

return v;

}

};

花花酱 LeetCode 1374. Generate a String With Characters That Have Odd Counts

By zxi on March 8, 2020

Given an integer n, return a string with n characters such that each character in such string occurs an odd number of times.

The returned string must contain only lowercase English letters. If there are multiples valid strings, return any of them.

Example 1:

Input: n = 4
Output: "pppz"
Explanation: "pppz" is a valid string since the character 'p' occurs three times and the character 'z' occurs once. Note that there are many other valid strings such as "ohhh" and "love".

Example 2:

Input: n = 2
Output: "xy"
Explanation: "xy" is a valid string since the characters 'x' and 'y' occur once. Note that there are many other valid strings such as "ag" and "ur".

Example 3:

Input: n = 7
Output: "holasss"

Constraints:

1 <= n <= 500

Solution: Greedy

if n is odd, return n ‘a’s.
otherwise, return n -1 ‘a’s and 1 ‘b’

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

C++

// Author: Huahua

class Solution {

public:

string generateTheString(int n) {

return n & 1 ? string(n, 'a') : string(n - 1, 'a') + "b";

}

};

Python3

# Author: Huahua

class Solution:

def generateTheString(self, n: int) -> str:

ans = ['a'] * n if n % 2 == 1 else ['a'] * (n - 1) + ['b']

return ''.join(ans)