From any string, we can form a subsequence of that string by deleting some number of characters (possibly no deletions).
Given two strings source
and target
, return the minimum number of subsequences of source
such that their concatenation equals target
. If the task is impossible, return -1
.
Example 1:
Input: source = "abc", target = "abcbc" Output: 2 Explanation: The target "abcbc" can be formed by "abc" and "bc", which are subsequences of source "abc".
Example 2:
Input: source = "abc", target = "acdbc" Output: -1 Explanation: The target string cannot be constructed from the subsequences of source string due to the character "d" in target string.
Example 3:
Input: source = "xyz", target = "xzyxz" Output: 3 Explanation: The target string can be constructed as follows "xz" + "y" + "xz".
Constraints:
- Both the
source
andtarget
strings consist of only lowercase English letters from "a"-"z". - The lengths of
source
andtarget
string are between1
and1000
.
A:
核心就是greedy ,每次在target里走的更远。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | class Solution { public: int shortestWay(string source, string target) { vector<bool> V(26,false); for(auto ch : source){ V[ch-'a'] = true; } int res = 1; int iS = 0; int nS = source.length(); for(int i =0;i<target.length(); i++){ char ch = target[i]; if(not V[ch-'a']){ return -1; } bool found = false; for(int step = 0;step<nS; step++){ if(source[iS] == ch){ found = true; } iS = (iS +1) ; if(iS == nS){ res++; iS = 0; } if(found){ break; } } } return iS == 0 ? res-1 : res; } }; |
No comments:
Post a Comment