Press "Enter" to skip to content

Posts published in “String”

花花酱 LeetCode 890. Find and Replace Pattern

Problem

You have a list ofĀ wordsĀ and aĀ pattern, and you want to know which words inĀ wordsĀ matches the pattern.

A word matches the pattern if there exists a permutation of lettersĀ pĀ so that after replacing every letterĀ xĀ in the pattern withĀ p(x), we get the desired word.

(Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.)

Return a list of the words inĀ wordsĀ that match the given pattern.

You may return the answer in any order.

Example 1:

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
since a and b map to the same letter.

Note:

  • 1 <= words.length <= 50
  • 1 <= pattern.length = words[i].lengthĀ <= 20

Solution: RememberĀ the last pos of each char.

Time complexity: O(n*l)

Space complexity: O(128) -> O(26)

C++

 

花花酱 LeetCode 551. Student Attendance Record I

Problem

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

  1. ‘A’Ā : Absent.
  2. ‘L’Ā : Late.
  3. ‘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)

Solution 2: Regex

 

花花酱 LeetCode 43. Multiply Strings

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:

  1. The length of bothĀ num1Ā andĀ num2Ā is < 110.
  2. BothĀ num1Ā andĀ num2Ā containĀ only digitsĀ 0-9.
  3. BothĀ num1Ā andĀ num2Ā do not contain any leading zero, except the number 0 itself.
  4. 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++

 

花花酱 LeetCode 709. To Lower Case

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++

Java

Python3

Python3 1-linear

花花酱 LeetCode 839. Similar String Groups

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:

  1. A.length <= 2000
  2. A[i].length <= 1000
  3. A.length * A[i].length <= 20000
  4. All words inĀ AĀ consist of lowercase letters only.
  5. All words inĀ AĀ have the same length and are anagrams of each other.
  6. 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++