Press "Enter" to skip to content

Posts published in “String”

花花酱 LeetCode 2452. Words Within Two Edits of Dictionary

You are given two string arrays, queries and dictionary. All words in each array comprise of lowercase English letters and have the same length.

In one edit you can take a word from queries, and change any letter in it to any other letter. Find all words from queries that, after a maximum of two edits, equal some word from dictionary.

Return a list of all words from queriesthat match with some word from dictionary after a maximum of two edits. Return the words in the same order they appear in queries.

Example 1:

Input: queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
Output: ["word","note","wood"]
Explanation:
- Changing the 'r' in "word" to 'o' allows it to equal the dictionary word "wood".
- Changing the 'n' to 'j' and the 't' to 'k' in "note" changes it to "joke".
- It would take more than 2 edits for "ants" to equal a dictionary word.
- "wood" can remain unchanged (0 edits) and match the corresponding dictionary word.
Thus, we return ["word","note","wood"].

Example 2:

Input: queries = ["yes"], dictionary = ["not"]
Output: []
Explanation:
Applying any two edits to "yes" cannot make it equal to "not". Thus, we return an empty array.

Constraints:

  • 1 <= queries.length, dictionary.length <= 100
  • n == queries[i].length == dictionary[j].length
  • 1 <= n <= 100
  • All queries[i] and dictionary[j] are composed of lowercase English letters.

Solution: Hamming distance + Brute Force

For each query word q, check the hamming distance between it and all words in the dictionary.

Time complexity: O(|q|*|d|*n)
Space complexity: O(1)

C++

花花酱 LeetCode 2451. Odd String Difference

You are given an array of equal-length strings words. Assume that the length of each string is n.

Each string words[i] can be converted into a difference integer array difference[i] of length n - 1 where difference[i][j] = words[i][j+1] - words[i][j] where 0 <= j <= n - 2. Note that the difference between two letters is the difference between their positions in the alphabet i.e. the position of 'a' is 0'b' is 1, and 'z' is 25.

  • For example, for the string "acb", the difference integer array is [2 - 0, 1 - 2] = [2, -1].

All the strings in words have the same difference integer array, except one. You should find that string.

Return the string in words that has different difference integer array.

Example 1:

Input: words = ["adc","wzy","abc"]
Output: "abc"
Explanation: 
- The difference integer array of "adc" is [3 - 0, 2 - 3] = [3, -1].
- The difference integer array of "wzy" is [25 - 22, 24 - 25]= [3, -1].
- The difference integer array of "abc" is [1 - 0, 2 - 1] = [1, 1]. 
The odd array out is [1, 1], so we return the corresponding string, "abc".

Example 2:

Input: words = ["aaa","bob","ccc","ddd"]
Output: "bob"
Explanation: All the integer arrays are [0, 0] except for "bob", which corresponds to [13, -13].

Constraints:

  • 3 <= words.length <= 100
  • n == words[i].length
  • 2 <= n <= 20
  • words[i] consists of lowercase English letters.

Solution: Comparing with first string.

Let us pick words[0] as a reference for comparison, assuming it’s valid. If we only found one instance say words[i], that is different than words[0], we know that words[i] is bad, otherwise we should see m – 1 different words which means words[0] itself is bad.

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

C++

花花酱 LeetCode 2315. Count Asterisks

You are given a string s, where every two consecutive vertical bars '|' are grouped into a pair. In other words, the 1st and 2nd '|' make a pair, the 3rd and 4th '|' make a pair, and so forth.

Return the number of '*' in sexcluding the '*' between each pair of '|'.

Note that each '|' will belong to exactly one pair.

Example 1:

Input: s = "l|*e*et|c**o|*de|"
Output: 2
Explanation: The considered characters are underlined: "l|*e*et|c**o|*de|".
The characters between the first and second '|' are excluded from the answer.
Also, the characters between the third and fourth '|' are excluded from the answer.
There are 2 asterisks considered. Therefore, we return 2.

Example 2:

Input: s = "iamprogrammer"
Output: 0
Explanation: In this example, there are no asterisks in s. Therefore, we return 0.

Example 3:

Input: s = "yo|uar|e**|b|e***au|tifu|l"
Output: 5
Explanation: The considered characters are underlined: "yo|uar|e**|b|e***au|tifu|l". There are 5 asterisks considered. Therefore, we return 5.

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters, vertical bars '|', and asterisks '*'.
  • s contains an even number of vertical bars '|'.

Solution: Counting

Count the number of bars so far, and only count ‘*’ when there are even number of bars on the left.

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

C++

花花酱 LeetCode 2269. Find the K-Beauty of a Number

The k-beauty of an integer num is defined as the number of substrings of num when it is read as a string that meet the following conditions:

  • It has a length of k.
  • It is a divisor of num.

Given integers num and k, return the k-beauty of num.

Note:

  • Leading zeros are allowed.
  • 0 is not a divisor of any value.

substring is a contiguous sequence of characters in a string.

Example 1:

Input: num = 240, k = 2
Output: 2
Explanation: The following are the substrings of num of length k:
- "24" from "240": 24 is a divisor of 240.
- "40" from "240": 40 is a divisor of 240.
Therefore, the k-beauty is 2.

Example 2:

Input: num = 430043, k = 2
Output: 2
Explanation: The following are the substrings of num of length k:
- "43" from "430043": 43 is a divisor of 430043.
- "30" from "430043": 30 is not a divisor of 430043.
- "00" from "430043": 0 is not a divisor of 430043.
- "04" from "430043": 4 is not a divisor of 430043.
- "43" from "430043": 43 is a divisor of 430043.
Therefore, the k-beauty is 2.

Constraints:

  • 1 <= num <= 109
  • 1 <= k <= num.length (taking num as a string)

Solution: Substring

Note: the substring can be 0, e.g. “00”

Time complexity: O((l-k)*k)
Space complexity: O(l + k) -> O(1)

C++

花花酱 LeetCode 2264. Largest 3-Same-Digit Number in String

You are given a string num representing a large integer. An integer is good if it meets the following conditions:

  • It is a substring of num with length 3.
  • It consists of only one unique digit.

Return the maximum good integer as a string or an empty string "" if no such integer exists.

Note:

  • substring is a contiguous sequence of characters within a string.
  • There may be leading zeroes in num or a good integer.

Example 1:

Input: num = "6777133339"
Output: "777"
Explanation: There are two distinct good integers: "777" and "333".
"777" is the largest, so we return "777".

Example 2:

Input: num = "2300019"
Output: "000"
Explanation: "000" is the only good integer.

Example 3:

Input: num = "42352338"
Output: ""
Explanation: No substring of length 3 consists of only one unique digit. Therefore, there are no good integers.

Constraints:

  • 3 <= num.length <= 1000
  • num only consists of digits.

Solution:

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

C++