[Leetcode 1055]Shortest Way to Form String

Posted on | In | Comments: | Views:

原题说明

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.

解题思路

O(MN)的解法较为直观，只需要用两个index i和j分别对应source和target的位置，然后对于每一个target[j],在source中找到对应的source[i], 并于每次i归零时计数即可。
这里介绍O(M + N)的解法：用一个二维哈希表（或者二维数组）index_to_next来表示当前source的index右边（包括index本身), 每一个字母第一次出现的位置的下一个位置。比如abbc，那么index[0]['a'] = 1, index[0]['b'] = 2, index[1]['b'] = 2, index[2]['b'] = 3...
从右向左遍历一遍source即可完成更新index_to_next, 然后遍历target，source和target的位置分别记为i和j，我们执行以下操作：

  1. index_to_next[0]当中是否存在target[j]，即整个source中是否存在j，不存在则返回-1
  2. index_to_next[i]当中是否存在target[j]，如果不存在，说明source在位置i右侧不存在target[j]，i应当归零从头开始找
  3. 如果i == 0，说明source被遍历了一边，返回值round应该增加1
  4. 更新i = index_to_next[i][target[i]] 即source中i右侧第一个target[j]的右侧的位置，这样相当于在source中读取了一个最近的target[i]
    最后返回round即可。

示例代码 (cpp)

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
class Solution {
public:
    int shortestWay(string source, string target) {
        // 第一个int：source当前index
        // 第二个int：souce中读取对应的char后，下一个index
        unordered_map<int, unordered_map<char, int>> index_to_next;
        index_to_next[source.size() - 1][source.back()] = 0;
        for (int i = source.size() - 2; i >= 0; --i) {
            index_to_next[i] = index_to_next[i + 1];
            index_to_next[i][source[i]] = i + 1;
        }
        int round = 0, i = 0;
        for (int j = 0; j < target.size(); ++j) {
            // 整个source中都没有target[j]，直接返回-1
            if (index_to_next[0].count(target[j]) == 0) {
                return -1;
            }
            // 当前source的位置i往后找不到target[j], 则应该将i归零重头开始找
            if (index_to_next[i].count(target[j]) == 0) {
                i = 0;
            }
            if (i == 0) {
                ++round;
            }
            i = index_to_next[i][target[j]];
        }
        return round;
    }
};

示例代码 (java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int shortestWay(String source, String target) {
    char[] cs = source.toCharArray(), ts = target.toCharArray();
    int[][] idx = new int[cs.length][26];
    idx[cs.length - 1][cs[cs.length - 1] - 'a'] = cs.length; 
    for (int i = cs.length - 2; i >= 0; i--) {
        idx[i] = Arrays.copyOf(idx[i + 1],26);
        idx[i][cs[i] - 'a'] = i + 1; 
    }
    int j = 0, res = 1;
    for (int i = 0; i < ts.length; i++) {
        if (j == cs.length) {
            j = 0;
            res++;
        }
        j = idx[j][ts[i] - 'a'];
        if (idx[0][ts[i] - 'a'] == 0) return -1;
        if (j == 0) {
            res++;
            i--;
        }
    }
    return res;
}

示例代码 (python)

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
# two pointer greedy O(MN)
class Solution:
    def shortestWay(self, source: str, target: str) -> int:
        num = 0
        t_p = 0
        while t_p < len(target):
            s_p = 0
            flag = False
            while s_p < len(source) and t_p < len(target):
                if source[s_p] == target[t_p]:
                    s_p += 1
                    t_p +=1
                    flag = True
                else:
                    s_p +=1
                    
            if flag == True:
                num +=1
            else:
                return -1
        return num 

# binary search O(NlogM)  
from collections import defaultdict
class Solution:
    
    def shortestWay(self, source: str, target: str) -> int:
        dic = defaultdict(list)
        for ind, char in enumerate(source):
            dic[char].append(ind)
        
        ind = 0
        ans = 1
        for char in target:
            if char not in dic:
                return -1
            else:
                ind, ans= self.binarysearch(source, char, ind, dic, ans)
                
        return ans
                    
    def binarysearch(self, source, char, ind, dic, ans):
        lis = dic[char]
        
        if lis[-1] < ind:
            ans += 1
            ind = 0
            
        l = 0
        r = len(lis)-1
        while l < r:
            mid = (l+r)//2
            if lis[mid] < ind:
                l = mid +1
            else:
                r = mid
    
        return lis[l]+1, ans

# O(N + M) char to index
class Solution:
    def shortestWay(self, source: str, target: str) -> int:
        source_set = set(source)
        
        lis = [[-1]*len(source) for _ in range(26)]
        for ind, char in enumerate(source):
            lis[ord(char)- ord('a')][ind] = ind
        
        for l in lis:
            pre = -1
            for i in range(len(l)-1,-1,-1):
                if l[i] != -1:
                    pre = l[i]
                else:
                    l[i] = pre
        ans = 1
        ind = 0
        for char in target:
            if char not in source_set:
                return -1
            if ind >= len(source):
                ind = 0
                ans += 1
            ind = lis[ord(char) - ord('a')][ind]
            if ind == -1:
                ind = lis[ord(char) - ord('a')][0]  
                ans += 1
            ind +=1

        return ans

# O(N + M)index to char
class Solution:
    def shortestWay(self, source: str, target: str) -> int:
        source_set = set(source)
        
        lis = [[-1]*26 for _ in range(len(source))]
        for i in range(len(lis)-1, -1, -1):
            if i == len(lis)-1:
                lis[i][ord(source[i]) - ord('a')] = i
            else:
                lis[i][:] = lis[i+1]
                lis[i][ord(source[i])-ord('a')] = i 
        
        ans = 1
        ind = 0
        for char in target:
            if char not in source_set:
                return -1
            if ind >= len(lis):
                ind = 0 
                ans +=1
                
            ind = lis[ind][ord(char)-ord('a')]
            if ind == -1:
                ans +=1
                ind = 0
                ind = lis[ind][ord(char)-ord('a')]
            
            ind +=1
            
        return ans

复杂度分析

时间复杂度: O(M + N)
空间复杂度: O(M)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！

Related Posts
------ 关注公众号：猩猩的乐园 ------