Posts tagged as “string”

花花酱 LeetCode 43. Multiply Strings

By zxi on July 26, 2018

Problem

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution: Simulation

Simulate multiplication one digit at a time.

Time complexity: O(l1*l2)

Space complexity: O(l1 + l2)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string multiply(string num1, string num2) {

const int l1 = num1.length();

const int l2 = num2.length();

string ans(l1 + l2, '0');

for (int i = l1 - 1; i >= 0; --i)

for (int j = l2 - 1; j >= 0; --j) {

int sum = (ans[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0');

ans[i + j + 1] = (sum % 10) + '0';

ans[i + j] += sum / 10;

}

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

if (ans[i] != '0' || i == ans.length() - 1) return ans.substr(i);

return "";

}

};

花花酱 LeetCode 712. Minimum ASCII Delete Sum for Two Strings

By zxi on July 20, 2018

Problem

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d]+101[e]+101[e] to the sum.  Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

Note:

0 < s1.length, s2.length <= 1000.
All elements of each string will have an ASCII value in [97, 122].

Solution: DP

Time complexity: O(l1 * l2)

Space complexity: O(l1 * l2)

C++

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int minimumDeleteSum(string s1, string s2) {

const int l1 = s1.length();

const int l2 = s2.length();

// dp[i][j] := min delete sum of (s1.substr(0, i), s2.substr(0, j))

vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));

for (int i = 1; i <= l1; ++i)

dp[i][0] = dp[i - 1][0] + s1[i - 1];

for (int j = 1; j <= l2; ++j)

dp[0][j] = dp[0][j - 1] + s2[j - 1];

for (int i = 1; i <= l1; ++i)

for (int j = 1; j <= l2; ++j)

if (s1[i - 1] == s2[j - 1])

// keep s1[i - 1] and s2[j - 1]

dp[i][j] = dp[i - 1][j - 1];

else

dp[i][j] = min(dp[i - 1][j] + s1[i - 1], // delete s1[i - 1]

dp[i][j - 1] + s2[j - 1]); // delete s2[j - 1]

return dp[l1][l2];

}

};

Solution2: Recursion + Memorization

Time complexity: O(l1 * l2)

Space complexity: O(l1 * l2)

C++

// Author: Huahua

// Running time: 20 ms

class Solution {

public:

int minimumDeleteSum(string s1, string s2) {

const int l1 = s1.length();

const int l2 = s2.length();

m_ = vector<vector<int>>(l1 + 1, vector<int>(l2 + 1, INT_MAX));

return dp(s1, l1, s2, l2);

}

private:

int dp(const string& s1, int i, const string& s2, int j) {

if (i == 0 && j == 0) return 0;

if (m_[i][j] != INT_MAX) return m_[i][j];

if (i == 0) // s1 is empty.

return m_[i][j] = dp(s1, i, s2, j - 1) + s2[j - 1];

if (j == 0) // s2 is empty

return m_[i][j] = dp(s1, i - 1, s2, j) + s1[i - 1];

if (s1[i - 1] == s2[j - 1]) // skip s1[i-1] / s2[j-1]

return m_[i][j] = dp(s1, i - 1, s2, j - 1);

return m_[i][j] = min(dp(s1, i - 1, s2, j) + s1[i - 1], // del s1[i-1]

dp(s1, i, s2, j - 1) + s2[j - 1]); // del s2[j-1]

}

vector<vector<int>> m_;

};

Problem

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

Note:
The vowels does not include the letter “y”.

Solution

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string reverseVowels(string s) {

int i = 0;

int j = s.size() - 1;

while (i < j) {

while (!isVowel(s[i]) && i < j) ++i;

while (!isVowel(s[j]) && i < j) --j;

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

}

return s;

}

private:

bool isVowel(char c) {

c = tolower(c);

return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';

}

};

花花酱 LeetCode 709. To Lower Case

By zxi on July 12, 2018

Problem

Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

string toLowerCase(string str) {

for (char &c : str)

if (c >= 'A' && c <= 'Z') c = c - 'A' + 'a';

return str;

}

};

Java

// Author: Huahua, 1 ms

class Solution {

public String toLowerCase(String str) {

char[] s = str.toCharArray();

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

if (s[i] >= 'A' && s[i] <= 'Z') s[i] = (char)(s[i] - 'A' + 'a');

return new String(s);

}

Python3

# Author: Huahua, 40 ms

class Solution:

def toLowerCase(self, str):

ans = ''

for c in str:

if c >= 'A' and c <= 'Z':

ans += chr(ord(c) + 32)

else:

ans += c

return ans

Python3 1-linear

# Author: Huahua, 68 ms

class Solution:

def toLowerCase(self, str):

return ''.join(chr(ord(c) + 32) if c >= 'A' and c <= 'Z' else c for c in str)

花花酱 LeetCode 839. Similar String Groups

By zxi on July 8, 2018

Problem

Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y.

For example, "tars" and "rats" are similar (swapping at positions 0 and 2), and "rats" and "arts" are similar, but "star" is not similar to "tars", "rats", or "arts".

Together, these form two connected groups by similarity: {"tars", "rats", "arts"} and {"star"}. Notice that "tars" and "arts" are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list A of strings. Every string in A is an anagram of every other string in A. How many groups are there?

Example 1:

Input: ["tars","rats","arts","star"]
Output: 2

Note:

A.length <= 2000
A[i].length <= 1000
A.length * A[i].length <= 20000
All words in A consist of lowercase letters only.
All words in A have the same length and are anagrams of each other.
The judging time limit has been increased for this question.

Solution: Brute Force + Union Find

Time Complexity: O(n^2 * L)

Space Complexity: O(n)

C++

// Author: Huahua

// Running time: 230 ms (<99.08%)

class DSU {

public:

DSU(int size):size_(size), parent_(size), rank_(size) {

iota(begin(parent_), end(parent_), 0);

}

int Find(int n) {

if (parent_[n] != n)

parent_[n] = Find(parent_[n]);

return parent_[n];

}

void Union(int x, int y) {

int px = Find(x);

int py = Find(y);

if (px == py) return;

if (rank_[py] > rank_[px])

swap(px, py);

else if (rank_[py] == rank_[px])

++rank_[px];

parent_[py] = px;

--size_;

}

int Size() const {

return size_;

}

private:

int size_;

vector<int> ranks_;

vector<int> parent_;

};

class Solution {

public:

int numSimilarGroups(vector<string>& A) {

DSU dsu(A.size());

for (int i = 0; i < A.size(); ++i)

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

if (similar(A[i], A[j]))

dsu.Union(i, j);

return dsu.Size();

}

private:

bool similar(const string& a, const string& b) {

int diff = 0;

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

if (a[i] != b[i] && ++diff > 2) return false;

return true;

}

};

Posts tagged as “string”

花花酱 LeetCode 43. Multiply Strings

Problem

Solution: Simulation

花花酱 LeetCode 712. Minimum ASCII Delete Sum for Two Strings

Problem

Solution: DP

Solution2: Recursion + Memorization

Related Problems

花花酱 LeetCode 345. Reverse Vowels of a String

Problem

Solution

花花酱 LeetCode 709. To Lower Case

Problem

Solution

C++

Java

Python3

Python3 1-linear

花花酱 LeetCode 839. Similar String Groups

Problem

Solution: Brute Force + Union Find