循环增长使字符串子序列等于另一个字符串
难度:
标签:
题目描述
You are given two 0-indexed strings str1 and str2.
In an operation, you select a set of indices in str1, and for each index i in the set, increment str1[i] to the next character cyclically. That is 'a' becomes 'b', 'b' becomes 'c', and so on, and 'z' becomes 'a'.
Return true if it is possible to make str2 a subsequence of str1 by performing the operation at most once, and false otherwise.
Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.
Example 1:
Input: str1 = "abc", str2 = "ad" Output: true Explanation: Select index 2 in str1. Increment str1[2] to become 'd'. Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.
Example 2:
Input: str1 = "zc", str2 = "ad" Output: true Explanation: Select indices 0 and 1 in str1. Increment str1[0] to become 'a'. Increment str1[1] to become 'd'. Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.
Example 3:
Input: str1 = "ab", str2 = "d" Output: false Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once. Therefore, false is returned.
Constraints:
1 <= str1.length <= 1051 <= str2.length <= 105str1andstr2consist of only lowercase English letters.
代码结果
运行时间: 82 ms, 内存: 16.3 MB
// Java Stream Solution
// 思路: 和Java解决方案相似，我们将使用Stream API进行操作和匹配。
import java.util.stream.IntStream;
public class SolutionStream {
public boolean canConvert(String str1, String str2) {
int[] j = {0};
int m = str2.length();
boolean result = IntStream.range(0, str1.length()).anyMatch(i -> {
char c1 = str1.charAt(i);
char c2 = str2.charAt(j[0]);
while (c1 != c2 && c1 != 'a' + (c2 - 'a') % 26) {
c1 = (char) ((c1 - 'a' + 1) % 26 + 'a');
}
if (c1 == c2) {
j[0]++;
}
return j[0] == m;
});
return result;
}
}解释
方法:
该题解依据的思路是通过单次循环遍历str1，同时尝试匹配str2中的字符。对于str1中的每个字符，我们检查它是否与str2中当前位置的字符相同，或者通过单次循环递增能变成str2中的该字符。如果条件满足，str2的索引向前移动一位。如果str2的所有字符都能按顺序在str1中找到匹配（包括循环递增的匹配），则返回true，否则遍历结束后返回false。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在单次循环递增的限制下，选择使用循环递增的映射而不是直接计算字符的下一个值？
▷🦆
在遍历str1的过程中，如果str2的当前字符与str1的当前字符不匹配，为什么不考虑跳过str1的更多字符来寻找匹配？
▷🦆
算法在遇到str1的字符可以循环递增匹配到str2的字符时，是如何决定是否执行这一操作的？
▷🦆
如果str2中的字符顺序与str1中的字符顺序不同，此算法是否仍然有效？例如str1为'abcd'且str2为'bac'，该算法能处理这种情况吗？
▷