花花酱 LeetCode 551. Student Attendance Record I

By zxi on August 17, 2018

Problem

You are given a string representing an attendance record for a student. The record only contains the following three characters:

‘A’ : Absent.
‘L’ : Late.
‘P’ : Present.

A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:

Input: "PPALLP"
Output: True

Example 2:

Input: "PPALLL"
Output: False

Solution1: Simulation

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

bool checkRecord(string s) {

int a{0};

int l{0};

for(char c: s) {

if (c == 'A') ++a;

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

else l=0;

if (a > 1 || l > 2) return false;

}

return true;

}

};

Solution 2: Regex

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

bool checkRecord(string s) {

return !std::regex_search(s, std::regex("A.*A|LLL"));

}

};

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

}

};

花花酱 LeetCode 567. Permutation in String

By zxi on June 28, 2018

Problem

题目大意：给你s1, s2，问你s2的子串中是否存在s1的一个排列。

https://leetcode.com/problems/permutation-in-string/description/

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

Solution: Sliding Window

Time Complexity: O(l1 + l2 * 26) = O(l1 + l2)

Space Complexity: O(26 * 2) = O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

bool checkInclusion(string s1, string s2) {

int l1 = s1.length();

int l2 = s2.length();

vector<int> c1(26);

vector<int> c2(26);

for (const char c : s1)

++c1[c - 'a'];

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

if (i >= l1)

--c2[s2[i - l1] - 'a'];

++c2[s2[i] - 'a'];

if (c1 == c2) return true;

}

return false;

}

};

Posts published in “String”

花花酱 LeetCode 551. Student Attendance Record I

Problem

Solution1: Simulation

Solution 2: Regex

花花酱 LeetCode 43. Multiply Strings

Problem

Solution: Simulation

花花酱 LeetCode 709. To Lower Case

Problem

Solution

C++

Java

Python3

Python3 1-linear

花花酱 LeetCode 839. Similar String Groups

Problem

Solution: Brute Force + Union Find

花花酱 LeetCode 567. Permutation in String

Problem

Solution: Sliding Window

Related Problems