使用循環增量使字串成為子序列

2825。使用循環增量使字串成為子序列

難度：中

主題： 兩個指針，字串

給你兩個0索引字串str1和str2。

在操作中，您在 str1 中選擇索引集合，並且對於該集合中的每個索引 i，將 str1[i] 遞增到下一個字元循環。即“a”變為“b”，“b”變為“c”，依此類推，“z”變為“a”。

如果可以透過執行操作至多一次使str2成為str1的子序列，則傳回true，否則傳回。

注意：字串的子序列是透過刪除原始字串中的一些（可能沒有）字元而不影響其餘字元的相對位置而形成的新字串。

範例1：

• 輸入： str1 = "abc", str2 = "ad"
• 輸出： true
• 解釋： 選擇 str1 中的索引 2。
  • 將 str1[2] 遞增為 'd'。
  • 因此，str1 變成“abd”，str2 現在是一個子序列。因此，傳回 true。

範例2：

• 輸入： str1 = "zc", str2 = "ad"
• 輸出： true
• 解釋： 選擇 str1 中的索引 0 和 1。
  • 將 str1[0] 遞增為 'a'。
  • 將 str1[1] 遞增為 'd'。
  • 因此，str1 變成“ad”，str2 現在是一個子序列。因此，傳回 true。

範例 3：

• 輸入： str1 = "ab", str2 = "d"
• 輸出： false
• 說明： 在這個例子中，可以證明使用最多一次的操作不可能使 str2 成為 str1 的子序列。
  • 因此回傳 false。

約束：

• 1 5
• 1 5
• str1 和 str2 僅由小寫英文字母組成。

提示：

1. 考慮我們將單獨遞增的索引。
2. 我們可以維護兩個指標：str1 的指標 i 和 str2 的指標 j，同時確保它們保持在字串的範圍內。
3. 如果str1[i]和str2[j]都匹配，或者如果遞增str1[i]匹配str2[j]，我們增加兩個指標；否則，我們只增加指標 i。
4. 在我們無法再找到匹配項之後，如果 j 位於 str2 的末尾，則可以使 str2 成為 str1 的子序列。

解：

我們需要檢查是否可以透過對 str1 中的任何字元執行最多一次循環增量操作來使 str2 成為 str1 的子序列：

解釋：

• 我們將使用兩個指針，i 代表 str1，j 代表 str2。
• 如果 str1[i] 處的字元與 str2[j] 匹配，我們將兩個指標向前移動。
• 如果 str1[i] 可以遞增以匹配 str2[j]（循環），我們嘗試匹配它們，然後移動兩個指標。
• 如果以上條件都不成立，我們只會移動str1的指標i。
• 最後，如果我們能夠匹配str2的所有字符，那麼就有可能使str2成為str1的子序列，否則不能。

讓我們用 PHP 實作這個解：2825。使用循環增量使字串成為子序列

<?php /**
 * @param String $str1
 * @param String $str2
 * @return Boolean
 */
function canMakeSubsequence($str1, $str2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$str1 = "abc";
$str2 = "ad";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true

$str1 = "zc";
$str2 = "ad";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: true

$str1 = "ab";
$str2 = "d";
echo canMakeSubsequence($str1, $str2) ? 'true' : 'false'; // Output: false
?>

解釋：

1. 兩個指標：i和j分別初始化為str1和str2的開頭。
2. 匹配邏輯：在循環內部，我們檢查 str1[i] 和 str2[j] 處的字元是否相同，或者是否可以循環遞增 str1[i] 來匹配 str2[j]。
   • 迴圈增量條件使用 (ord($str1[$i]) 1 - ord('a')) % 26 處理，它檢查 str1[i] 是否可以遞增以符合 str2[j]。
3. 子序列檢查：如果我們完全迭代了str2（即j == m），則表示str2是str1的子序列。否則就不是了。

時間複雜度：

• 此演算法迭代str1一次，而str2中的每個字元只檢查一次，因此時間複雜度為O(n)，其中n是str1的長度。

空間複雜度：

• 空間複雜度為O(1)，因為我們只使用幾個指針，並且不需要依賴輸入大小的額外空間。

該解決方案有效地檢查是否可以透過最多一次循環增量操作使 str2 成為 str1 的子序列。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是使用循環增量使字串成為子序列的詳細內容。更多資訊請關注PHP中文網其他相關文章！