Huahua’s Tech Road

花花酱 LeetCode 1639. Number of Ways to Form a Target String Given a Dictionary

By zxi on October 31, 2020

You are given a list of strings of the same length words and a string target.

Your task is to form target using the given words under the following rules:

target should be formed from left to right.
To form the i^th character (0-indexed) of target, you can choose the k^th character of the j^th string in words if target[i] = words[j][k].
Once you use the k^th character of the j^th string of words, you can no longer use the x^th character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.
Repeat the process until you form the string target.

Notice that you can use multiple characters from the same string in words provided the conditions above are met.

Return the number of ways to form target from words. Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")

Example 2:

Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")

Example 3:

Input: words = ["abcd"], target = "abcd"
Output: 1

Example 4:

Input: words = ["abab","baba","abba","baab"], target = "abba"
Output: 16

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 1000
All strings in words have the same length.
1 <= target.length <= 1000
words[i] and target contain only lowercase English letters.

Solution: DP

dp[i][j] := # of ways to form target[0~j] where the j-th letter is from the i-th column of words.
count[i][j] := # of words that have word[i] == target[j]

dp[i][j] = dp[i-1][j-1] * count[i][j]

Time complexity: O(mn)
Space complexity: O(mn) -> O(n)

C++

class Solution {

public:

int numWays(vector<string>& words, string target) {

constexpr int kMod = 1e9 + 7;

const int n = target.length();

const int m = words[0].length();

vector<long> dp(n); // dp[j] = # of ways to form t[0~j]

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

vector<int> count(26);

for (const string& word: words)

++count[word[i] - 'a'];

for (int j = min(i, n - 1); j >= 0; --j)

dp[j] = (dp[j] + (j > 0 ? dp[j - 1] : 1) *

count[target[j] - 'a']) % kMod;

}

return dp[n - 1];

}

};

花花酱 LeetCode 1638. Count Substrings That Differ by One Character

By zxi on October 31, 2020

Given two strings s and t, find the number of ways you can choose a non-empty substring of s and replace a single character by a different character such that the resulting substring is a substring of t. In other words, find the number of substrings in s that differ from some substring in t by exactly one character.

For example, the underlined substrings in "computer" and "computation" only differ by the 'e'/'a', so this is a valid way.

Return the number of substrings that satisfy the condition above.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "aba", t = "baba"
Output: 6
Explanation: The following are the pairs of substrings from s and t that differ by exactly 1 character:
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
The underlined portions are the substrings that are chosen from s and t.

Example 2:

Input: s = "ab", t = "bb"
Output: 3
Explanation: The following are the pairs of substrings from s and t that differ by 1 character:
("ab", "bb")
("ab", "bb")
("ab", "bb")
The underlined portions are the substrings that are chosen from s and t.

Example 3:

Input: s = "a", t = "a"
Output: 0

Example 4:

Input: s = "abe", t = "bbc"
Output: 10

Constraints:

1 <= s.length, t.length <= 100
s and t consist of lowercase English letters only.

Solution1: All Pairs + Prefix Matching

match s[i:i+p] with t[j:j+p], is there is one missed char, increase the ans, until there are two miss matched chars or reach the end.

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

C++

class Solution {

public:

int countSubstrings(string s, string t) {

const int m = s.length();

const int n = t.length();

int ans = 0, diff = 0;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j, diff = 0)

for (int p = 0; i + p < m && j + p < n && diff <= 1; ++p)

if ((diff += (s[i + p] != t[j + p])) == 1) ++ans;

return ans;

}

};

Solution 2: Continuous Matching

Start matching s[0] with t[j] and s[i] with t[0]

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

C++

class Solution {

public:

int countSubstrings(string s, string t) {

const int m = s.length();

const int n = t.length();

int ans = 0;

auto helper = [&](int i, int j) {

for (int cur = 0, pre = 0; i < m && j < n; ++i, ++j) {

++cur;

if (s[i] != t[j]) {

pre = cur;

cur = 0;

}

ans += pre;

}

};

for (int i = 0; i < m; ++i) helper(i, 0);

for (int j = 1; j < n; ++j) helper(0, j);

return ans;

}

};

花花酱 LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points

By zxi on October 31, 2020

Given n points on a 2D plane where points[i] = [x_i, y_i], Return the widest vertical area between two points such that no points are inside the area.

A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.

Note that points on the edge of a vertical area are not considered included in the area.

Example 1:

Input: points = [[8,7],[9,9],[7,4],[9,7]]
Output: 1
Explanation: Both the red and the blue area are optimal.

Example 2:

Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
Output: 3

Constraints:

n == points.length
2 <= n <= 10⁵
points[i].length == 2
0 <= x_i, y_i <= 10⁹

Solution: Sort by x coordinates

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

C++

class Solution {

public:

int maxWidthOfVerticalArea(vector<vector<int>>& points) {

sort(begin(points), end(points), [](const auto& p1, const auto& p2) {

return p1[0] != p2[0] ? p1[0] < p2[0] : p1[1] < p2[1];

});

int ans = 0;

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

ans = max(ans, points[i][0] - points[i - 1][0]);

return ans;

}

};

花花酱 LeetCode 1636. Sort Array by Increasing Frequency

By zxi on October 31, 2020

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.

Return the sorted array.

Example 1:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.

Example 2:

Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

Example 3:

Input: nums = [-1,1,-6,4,5,-6,1,4,1]
Output: [5,-1,4,4,-6,-6,1,1,1]

Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Solution: Hashtable + Sorting

Use a hashtable to track the frequency of each number.

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

C++

class Solution {

public:

vector<int> frequencySort(vector<int>& nums) {

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

sort(begin(nums), end(nums), [&](int a, int b) {

if (freq[a] != freq[b]) return freq[a] < freq[b];

return a > b;

});

return nums;

}

};

花花酱 LeetCode 61. Rotate List

By zxi on October 28, 2020

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

Solution: Find the prev of the new head

Step 1: Get the tail node T while counting the length of the list.
Step 2: k %= l, k can be greater than l, rotate k % l times has the same effect.
Step 3: Find the previous node P of the new head N by moving (l – k – 1) steps from head
Step 4: set P.next to null, T.next to head and return N

Time complexity: O(n) n is the length of the list
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

ListNode* rotateRight(ListNode* head, int k) {

if (!head) return head;

int l = 1;

ListNode* tail = head;

while (tail->next) { tail = tail->next; ++l; }

k %= l;

if (k == 0) return head;

ListNode* prev = head;

while (--l > k) prev = prev->next;

ListNode* new_head = prev->next;

tail->next = head;

prev->next = nullptr;

return new_head;

}

};

Java

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

* }

class Solution {

public ListNode rotateRight(ListNode head, int k) {

if (head == null) return null;

int l = 1;

ListNode tail = head;

while (tail.next != null) {

tail = tail.next;

++l;

}

k %= l;

if (k == 0) return head;

ListNode prev = head;

for (int i = 0; i < l - k - 1; ++i) {

prev = prev.next;

}

ListNode new_head = prev.next;

prev.next = null;

tail.next = head;

return new_head;

}

Python3

class Solution:

def rotateRight(self, head: ListNode, k: int) -> ListNode:

if not head: return head

tail = head

l = 1

while tail.next:

tail = tail.next

l += 1

k = k % l

if k == 0: return head

prev = head

for _ in range(l - k - 1): prev = prev.next

new_head = prev.next

tail.next = head

prev.next = None

return new_head

Huahua's Tech Road

花花酱 LeetCode 1639. Number of Ways to Form a Target String Given a Dictionary

Solution: DP

C++

花花酱 LeetCode 1638. Count Substrings That Differ by One Character

Solution1: All Pairs + Prefix Matching

C++

Solution 2: Continuous Matching

C++

花花酱 LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points

Solution: Sort by x coordinates

C++

花花酱 LeetCode 1636. Sort Array by Increasing Frequency

Solution: Hashtable + Sorting

C++

花花酱 LeetCode 61. Rotate List

Solution: Find the prev of the new head

C++

Java

Python3