狗家高频1055的解法没看懂

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 and target strings consist of only lowercase English letters from "a"-"z".
The lengths of source and target string are between 1 and 1000.

1. class Solution {
   
2.     public int shortestWay(String source, String target) {
   
3.         char[] sc = source.toCharArray(), ta = target.toCharArray();
   
4.         boolean[] map = new boolean[26];
   
5.         for (char c : sc) {
   
6.             map[c - 'a'] = true;
   
7.         }
   
8.         
   
9.         int j = 0, res = 1;
   
10.         for (int i = 0; i < ta.length; i ++, j ++) {
    
11.             if (!map[ta[i] - 'a']) return -1;
    
12.             while (j < sc.length && sc[j] != ta[i]) j ++;
    
13.             if (j == sc.length) {
    
14.                 res ++;
    
15.                 j = -1;
    
16.                 i --;
    
17.             }
    
18.         }
    
19.         return res;
    
20.     }
    
21. }

复制代码

Greedy

Use two pointers, one for source: i, one for target: j. While j scan through target, try to match each char of j in source by moving i. Count how many times i goes through source end.


  x y z
    i

  x z y x z
       j

比如这样的时候，为什么j就qualified的了？

xz + y + xz啊。j还是移动了的

一遍一遍扫呗有啥看不懂的, 你问题在哪

哈哈，我还只会暴力n方的解决法。

codeyy 发表于 2019-11-1 06:13
哈哈，我还只会暴力n方的解决法。

上面给的解法就是n方，或者更准确的：n*m

为了做到O(n+m)，需要将source改写为一个len(source)*26的二维数组，记录在source每个index处，下一个指定字符c在什么位置，这样在source上的iteration就是O(1)了

楼上说的对，其实就是类似 KMP 的 next 数组