文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

對于任何字符串，我們可以通過刪除其中一些字符（也可能不刪除）來構造該字符串的子序列。

給定源字符串 source 和目標字符串 target，找出源字符串中能通過串聯形成目標字符串的子序列的最小數量。
如果無法通過串聯源字符串中的子序列來構造目標字符串，則返回 -1。

示例 1： 輸入：source = "abc", target = "abcbc" 輸出：2 解釋：目標字符串 "abcbc" 可以由 "abc" 和 "bc" 形成， 它們都是源字符串 "abc" 的子序列。示例 2： 輸入：source = "abc", target = "acdbc" 輸出：-1 解釋：由于目標字符串中包含字符 "d"，所以無法由源字符串的子序列構建目標字符串。示例 3： 輸入：source = "xyz", target = "xzyxz" 輸出：3 解釋：目標字符串可以按如下方式構建： "xz" + "y" + "xz"。提示： source 和 target 兩個字符串都只包含 "a"-"z" 的英文小寫字母。 source 和 target 兩個字符串的長度介于 1 和 1000 之間。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shortest-way-to-form-string
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

class Solution { public:int shortestWay(string source, string target) {int i = 0, j = 0, k, count = 0;while(j < target.size()){k = j;//記錄開始的地方count++;i = 0;//新的開始while(i < source.size())//遍歷字符串{if(source[i] == target[j])//可以給到target{i++;j++;}elsei++;//刪除某字符}if(j == k)//沒有填入一個字符到targetreturn -1;}return count;} };

0 ms 6.6 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1055. 形成字符串的最短路径（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。