---
# System prepended metadata

title: 1055. Shortest Way to Form String
tags: [Leetcode, Medium, State Machine, Greedy]

---

# 1055. Shortest Way to Form String
###### tags: `Leetcode` `Medium` `Greedy` `State Machine`
Link: https://leetcode.com/problems/shortest-way-to-form-string/
## 思路
### Two Pointers $O(MN)$
用一个pointer遍历```s``` 另一个pointer遍历```t```
用一个array记录存在的所有字符 这样如果拿到一个不存在的字符直接返回-1
### Binary Search $O(MN)$
把每个character出现的位置都存下来
由于存的时候就是按照从小到大的顺序存的
所以 我们可以用binary search找到距离最近的下一个字符出现的位置
### Greedy - State Machine $O(26N)$
和[0524. Longest Word in Dictionary through Deleting](https://hackmd.io/hZKZPqUxRyaISwaadQKxeg)有点像
先得到```next[i][ch]```表示```s```中位置```i-1```右边第一个出现```ch```的位置 这里的时间复杂度是```O(26N) ```
所以```next[0]```里面存着```s```里面所有出现过的字符的位置
```next[n]```全都是-1 因为后面不再有东西了
然后我们每次next = next[idx][curr]找到距离当前位置最近的下一个字符的位置在哪
如果遇到-1 说明我们已经找到source的尾巴了 这时候需要ans+1 从头开始找
但是如果next[0][ch]也等于-1 说明这个character根本不存在 直接返回-1
## Code
### Two Pointers
```java=
class Solution {
    public int shortestWay(String source, String target) {
        int m = source.length(), n = target.length();
        int ans = 1;
        boolean[] exist = new boolean[26];
        for(int i=0; i<m; i++){
            exist[source.charAt(i)-'a'] = true;
        }
        int j=0;
        for(int i=0; i<n; i++){
            if(!exist[target.charAt(i)-'a']) return -1;
            while(j<m){
                if(source.charAt(j)==target.charAt(i)) break;
                j++;
            }
            if(j==m){
                j=-1;
                i--;
                ans++;
            }
            j++;
        }
        return ans;
    }
}
```
### Binary Search $O(MN)$
```java=
class Solution {
    public int shortestWay(String source, String target) {
        List<List<Integer>> pos = new ArrayList<>();
        for(int i=0; i<26; i++) pos.add(new ArrayList<>());
        for(int i=0; i<source.length(); i++){
            pos.get(source.charAt(i)-'a').add(i);
        }
        int idx = -1;
        int ans = 1;
        for(int i=0; i<target.length(); i++){
            char c = target.charAt(i);
            if(pos.get(c-'a').size()==0) return -1;
            idx = binarySearch(pos.get(c-'a'), idx);
            if(idx==-1){
                ans++;
                i--;
            }
        }
        return ans;
    }
    private int binarySearch(List<Integer> pos, int idx){
        int start = 0;
        int end = pos.size();
        while(start<end){
            int mid = start+(end-start)/2;
            if(pos.get(mid)<=idx) start = mid+1;
            else end = mid;
        }
        return start==pos.size()?-1:pos.get(start);
    }
}
```
### Greedy - State Machine
```python=
class Solution:
    def shortestWay(self, source: str, target: str) -> int:
        n = len(source)
        nextPos = [[-1 for _ in range(26)] for i in range(n+1)]
        for i in range(n-1, -1, -1):
            for j in range(26):
                nextPos[i][j] = nextPos[i+1][j]
            nextPos[i][ord(source[i])-ord('a')] = i+1
        
        ans = 1
        idx = 0
        for i in range(len(target)):
            idx = nextPos[idx][ord(target[i])-ord('a')]
            if idx==-1:
                ans += 1
                idx = nextPos[0][ord(target[i])-ord('a')]
                if idx==-1: return -1
        return ans
```
```java=
class Solution {
    public int shortestWay(String source, String target) {
        int n = source.length();
        int[][] next = new int[n+1][26];
        Arrays.fill(next[n], -1);
        for(int i=n-1; i>=0; i--){
            for(int j=0; j<26; j++){
                next[i][j] = next[i+1][j];
                next[i][source.charAt(i)-'a'] = i+1;
            }
        }
        int ans = 1;
        int idx = 0;
        for(int i=0; i<target.length(); i++){
            idx = next[idx][target.charAt(i)-'a'];
            if(idx==-1){
                ans++;
                idx = next[0][target.charAt(i)-'a'];
                if(idx==-1) return -1;
            }
        }
        return ans;
    }
}
```