# 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 = next[idx][curr]找到距离当前位置最近的下一个字符的位置在哪
如果遇到-1 说明我们已经找到source的尾巴了 这时候需要ans+1 从头开始找
但是如果next[0][ch]也等于-1 说明这个character根本不存在 直接返回-1
## Code
### Two Pointers

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)$

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

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

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;
}
}