LeetCode 1055 Shortest Way to Form String 四种解法全解析子序列判定、双指针、倒排索引与 2D 下一出现位置表【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 articles/shortest-way-to-form-string.md 为核心骨架系统讲解如何计算将字符串target作为子序列拼出所需的最少source拷贝份数。文章依次给出暴力拼接、双指针模拟、倒排索引 二分查找、2D 预计算表四种思路并配套多语言实现、复杂度对比与常见陷阱分析。读完你不仅能 AC 该题还能把子序列判定 循环扫描 跳表加速这一套方法论迁移到其他字符串与贪心匹配场景。前置知识在动手之前请确保你对以下四个基础概念足够熟悉它们是理解全部四种解法的地基子序列Subsequence理解一个字符串是另一个字符串的子序列意味着什么——不要求连续只要求按相对顺序出现。可参考仓库内 is-subsequence.md 与 longest-common-subsequence.md 两篇文章加深理解。双指针技巧Two Pointers用两个指针分别遍历、比较两个字符串线性完成匹配是解法一与解法二的核心工具。二分查找Binary Search在有序数组中快速定位元素用于解法三中对下一出现位置的 O(log S) 查询。预计算 / 动态规划Precomputation / DP预先构建查找表使匹配阶段对下一个字符位置的查询降到 O(1)这是解法四的本质。问题定义与题目理解本题的目标是给定两个字符串source和target返回使得target成为source重复拼接若干次后所得字符串的子序列所需的最少拷贝次数若无论如何拼接都不可能即target中存在source没有的字符返回-1。关键点在于拼接次数从1起步——单个source本身就是拼接一次子序列而非子串因此每份拷贝之间不要求字符连续跨拷贝匹配是允许的不可能情形唯一判定条件target中存在某个字符在source中从未出现。一旦判定不可能直接返回-1这是所有解法共用的第一道关卡。根据仓库内 articles/README.md 的规范每篇文章应当覆盖 NeetCode 视频中尽可能全的解法并给出时间/空间复杂度本文即按此标准组织四种递进式解法。解法一逐份拼接直到 target 成为子序列Concatenate until Subsequence直觉Intuition最直白、最符合题目字面描述的思路既然答案就是需要拼接多少份source那就真的去拼接。先把source里的字符放进一个集合逐一检查target的每个字符一旦发现缺失字符立刻返回-1。随后从concatenatedSource source、count 1开始每轮判断target是否已是拼接串的子序列不是就再追加一份source并把count加一直到满足条件为止。算法步骤Algorithm构建source中所有字符的集合用布尔数组亦可遍历target每个字符若任一字符不在集合中返回-1初始化concatenatedSource sourcecount 1循环只要target还不是concatenatedSource的子序列向concatenatedSource追加一份sourcecount 1返回count。代码实现class Solution: def shortestWay(self, source: str, target: str) - int: # 判断 to_check 是否为 in_string 的子序列 def is_subsequence(to_check, in_string): i j 0 while i len(to_check) and j len(in_string): if to_check[i] in_string[j]: i 1 j 1 return i len(to_check) # source 中所有字符的集合也可用布尔数组 source_chars set(source) # 检查 target 的每个字符是否都存在于 source缺一即返回 -1 for char in target: if char not in source_chars: return -1 # 逐份拼接 source直到 target 成为拼接串的子序列 concatenated_source source count 1 while not is_subsequence(target, concatenated_source): concatenated_source source count 1 return countclass Solution { public: int shortestWay(string source, string target) { // 布尔数组标记 source 中出现过的字符 bool sourceChars[26] {false}; for (char c : source) sourceChars[c - a] true; // 任一 target 字符缺失则不可能返回 -1 for (char c : target) { if (!sourceChars[c - a]) return -1; } // 拼接直到 target 是拼接串的子序列 string concatenatedSource source; int count 1; while (!isSubsequence(target, concatenatedSource)) { concatenatedSource source; count; } return count; } // 判断 toCheck 是否为 inString 的子序列 bool isSubsequence(string toCheck, string inString) { int i 0, j 0; while (i toCheck.length() j inString.length()) { if (toCheck[i] inString[j]) i; j; } return i toCheck.length(); } };func shortestWay(source string, target string) int { // 布尔数组标记 source 中出现过的字符 sourceChars : make([]bool, 26) for _, c : range source { sourceChars[c-a] true } // 任一 target 字符缺失则不可能返回 -1 for _, c : range target { if !sourceChars[c-a] { return -1 } } // 判断 toCheck 是否为 inString 的子序列 isSubsequence : func(toCheck, inString string) bool { i, j : 0, 0 for i len(toCheck) j len(inString) { if toCheck[i] inString[j] { i } j } return i len(toCheck) } // 拼接直到 target 成为拼接串的子序列 concatenatedSource : source count : 1 for !isSubsequence(target, concatenatedSource) { concatenatedSource source count } return count }其余语言Java、JavaScript、C#、Kotlin、Swift、Rust的实现与上述结构完全一致先做字符存在性检查再用双指针子序列判定 循环拼接可参考原文档 articles/shortest-way-to-form-string.md 中的完整 tabs 版本。复杂度分析时间复杂度O(T² · S)其中 S 为source长度、T 为target长度。最坏情况下每次追加一份source都要重新做一次 O(S·T) 的子序列判定而最多需要拼接 T 次target中每个字符都要消耗一整份拷贝时达到上界故总体约为 O(T · (S·T)) O(T²·S)。空间复杂度O(T·S)因为最坏情况下concatenatedSource的长度会膨胀到 T·S。其中 S 是source的长度T 是target的长度。解法二双指针循环扫描Two Pointers直觉Intuition解法一反复拼接出巨大字符串的做法既浪费内存又重复计算。解法二改为模拟同一过程用单个指针sourceIterator在source上线性移动配合取模运算把source当作环形字符串来虚拟拼接。每次需要找target的某个字符时就向前推进sourceIterator直到命中当指针因取模回到开头0说明进入新一轮扫描此时count加一。整个过程无需真正拼接任何字符串。算法步骤Algorithm构建source的字符集合target中任一字符缺失则返回-1初始化sourceIterator 0、count 0遍历target每个字符若sourceIterator 0说明即将开始一轮新的扫描count 1当source[sourceIterator]不等于当前字符时用sourceIterator (sourceIterator 1) % m前进若前进后回到0count 1命中当前字符后sourceIterator (sourceIterator 1) % m再前进一位为匹配下一个字符做准备返回count。代码实现class Solution: def shortestWay(self, source: str, target: str) - int: # source 中所有字符的集合也可用布尔数组 source_chars set(source) # 检查 target 的每个字符是否都存在于 source for char in target: if char not in source_chars: return -1 # source 长度用于取模回绕到开头 m len(source) # source 上的扫描指针 source_iterator 0 # 完整扫描 source 的轮数。当在寻找某个 target 字符的过程中 # source_iterator 再次回到起点时就说明开启了一轮新扫描。 count 0 for char in target: # 指针在起点即将开始新一轮扫描 if source_iterator 0: count 1 # 线性扫描 source直到找到当前字符 while source[source_iterator] ! char: # 取模前进实现环形回绕 source_iterator (source_iterator 1) % m # 回绕到起点说明开启新的一轮 if source_iterator 0: count 1 # 找到字符后前进一位注意此时不要立刻增加 count # 因为还不确定 target 是否还有剩余字符。 source_iterator (source_iterator 1) % m return countclass Solution { public: int shortestWay(string source, string target) { // 布尔数组标记 source 中出现过的字符 bool sourceChars[26] {false}; for (char c : source) sourceChars[c - a] true; // 任一 target 字符缺失则不可能 for (char c : target) { if (!sourceChars[c - a]) return -1; } int m source.length(); // 用于取模回绕 int sourceIterator 0; // source 扫描指针 int count 0; // 完整扫描轮数 for (char c : target) { if (sourceIterator 0) count; // 开启新一轮 while (source[sourceIterator] ! c) { // 线性查找 sourceIterator (sourceIterator 1) % m; if (sourceIterator 0) count; // 回绕计一轮 } sourceIterator (sourceIterator 1) % m; // 命中后前进 } return count; } };class Solution { shortestWay(source, target) { // 布尔数组标记 source 中出现过的字符 let sourceChars new Array(26).fill(false); for (let c of source) { sourceChars[c.charCodeAt(0) - a.charCodeAt(0)] true; } // 任一 target 字符缺失则不可能 for (let c of target) { if (!sourceChars[c.charCodeAt(0) - a.charCodeAt(0)]) { return -1; } } let m source.length; // 用于取模回绕 let sourceIterator 0; // source 扫描指针 let count 0; // 完整扫描轮数 for (let c of target) { if (sourceIterator 0) count; // 开启新一轮 while (source[sourceIterator] ! c) { // 线性查找 sourceIterator (sourceIterator 1) % m; if (sourceIterator 0) count; // 回绕计一轮 } sourceIterator (sourceIterator 1) % m; // 命中后前进 } return count; } }复杂度分析时间复杂度O(S·T)。对target的每个字符最坏情况下指针要在source上绕一整圈S 步才能命中故总量级为 O(S·T)。虽然表面上比解法一更差或持平但它省去了拼接与重复判定实际常数更小且空间占用恒为 O(1)。空间复杂度O(1)只用了常数个变量。其中 S 是source的长度T 是target的长度。解法三倒排索引 二分查找Inverted Index and Binary Search直觉Intuition解法二对target的每个字符都可能线性扫过整个source仍有冗余。解法三通过预计算倒排索引把找下一个位置变成二分查找先为source中每种字符维护一个升序排列的下标列表。匹配target的字符 c 时只需在charToIndices[c]中用二分查找定位第一个 sourceIterator的下标若列表已耗尽越界说明这一轮扫描找不到需要回绕到开头、开启新的一轮。算法步骤Algorithm构建倒排索引对source中每个字符存一个按升序排列的位置列表charToIndices[c]初始化sourceIterator 0、count 1遍历target每个字符若charToIndices[c]为空字符不存在返回-1在charToIndices[c]中二分查找第一个 sourceIterator的下标若查找结果越界所有出现位置都已越过count 1并取列表第一个位置indices[0] 1作为新的sourceIterator否则取indices[index] 1返回count。代码实现class Solution { public int shortestWay(String source, String target) { // 每种字符在 source 中的下标列表 ArrayListInteger[] charToIndices new ArrayList[26]; for (int i 0; i source.length(); i) { char c source.charAt(i); if (charToIndices[c - a] null) { charToIndices[c - a] new ArrayList(); } charToIndices[c - a].add(i); } int sourceIterator 0; // source 扫描指针 int count 1; // 需要的完整扫描轮数 for (char c : target.toCharArray()) { // 字符不在 source 中不可能 if (charToIndices[c - a] null) { return -1; } // 二分查找第一个 sourceIterator 的下标 ArrayListInteger indices charToIndices[c - a]; int index Collections.binarySearch(indices, sourceIterator); // 未命中时binarySearch 返回 -(插入点)-1还原为插入点 if (index 0) { index -index - 1; } // 插入点在列表末尾本轮找不到开启新一轮 if (index indices.size()) { count; sourceIterator indices.get(0) 1; } else { sourceIterator indices.get(index) 1; } } return count; } }class Solution { public: int shortestWay(string source, string target) { // 每种字符在 source 中的下标列表 vectorint charToIndices[26]; for (int i 0; i source.size(); i) { charToIndices[source[i] - a].push_back(i); } int sourceIterator 0; // source 扫描指针 int count 1; // 需要的完整扫描轮数 for (int i 0; i target.size(); i) { // 字符不在 source 中不可能 if (charToIndices[target[i] - a].size() 0) { return -1; } // lower_bound 找第一个 sourceIterator 的位置 vectorint indices charToIndices[target[i] - a]; int index lower_bound(indices.begin(), indices.end(), sourceIterator) - indices.begin(); // 越界本轮找不到开启新一轮 if (index indices.size()) { count; sourceIterator indices[0] 1; } else { sourceIterator indices[index] 1; } } return count; } };class Solution: def shortestWay(self, source: str, target: str) - int: # 每种字符在 source 中的下标列表 char_to_indices [[] for _ in range(26)] for i, c in enumerate(source): char_to_indices[ord(c) - ord(a)].append(i) # 自定义二分查找返回第一个 target 的下标无则返回 len(arr) def lower_bound(arr, target): left, right 0, len(arr) while left right: mid (left right) // 2 if arr[mid] target: left mid 1 else: right mid return left source_iterator 0 # source 扫描指针 count 1 # 需要的完整扫描轮数 for c in target: idx ord(c) - ord(a) # 字符不在 source 中不可能 if not char_to_indices[idx]: return -1 indices char_to_indices[idx] pos lower_bound(indices, source_iterator) # 越界本轮找不到开启新一轮 if pos len(indices): count 1 source_iterator indices[0] 1 else: source_iterator indices[pos] 1 return count复杂度分析时间复杂度O(S T·log S)。建索引耗时 O(S)匹配阶段每个字符一次二分查找耗时 O(log S)共 T 次。空间复杂度O(S)用于存储所有字符的位置列表。其中 S 是source的长度T 是target的长度。解法四2D 数组预计算下一出现位置2D Array / Next Occurrence Table直觉Intuition解法三的二分查找已经很快但还可以把查询压缩到 O(1)预计算一个二维表nextOccurrence[i][c]表示source中位置 i 及其之后字符 c 第一次出现的位置。该表从右往左用递推关系填充本质是动态规划每一行先复制下一行的全部值再把当前位置字符的条目更新为当前位置。匹配阶段每次查询都是 O(1) 的数组访问匹配完成后总复杂度只有 O(S T)。算法步骤Algorithm创建nextOccurrence尺寸为source.length × 26初始化最后一行全部置为-1再把source最后一个字符对应的条目设为source.length - 1从右往左填充其余行把nextOccurrence[i1]的值整体复制到nextOccurrence[i]更新nextOccurrence[i][source[i]] i初始化sourceIterator 0、count 1遍历target每个字符 c若nextOccurrence[0][c] -1说明 c 在source中不存在返回-1若sourceIterator source.length或nextOccurrence[sourceIterator][c] -1当前位置之后没有 c 了count 1并把sourceIterator重置为0令sourceIterator nextOccurrence[sourceIterator][c] 1返回count。代码实现class Solution: def shortestWay(self, source: str, target: str) - int: source_length len(source) # next_occurrence[i][c]source 在位置 i 及之后字符 c 首次出现的位置 next_occurrence [defaultdict(int) for idx in range(source_length)] # 基础情形最后一行只记录最后一个字符 next_occurrence[source_length - 1][source[source_length - 1]] source_length - 1 # 从右往左递推填充 for idx in range(source_length - 2, -1, -1): next_occurrence[idx] next_occurrence[idx 1].copy() next_occurrence[idx][source[idx]] idx source_iterator 0 count 1 for char in target: # 字符不存在于 source不可能 if char not in next_occurrence[0]: return -1 # 已到 source 末尾或当前位置之后没有该字符回绕并开启新一轮 if (source_iterator source_length or char not in next_occurrence[source_iterator]): count 1 source_iterator 0 # O(1) 查询下一出现位置并前进 source_iterator next_occurrence[source_iterator][char] 1 return countclass Solution { public int shortestWay(String source, String target) { // nextOccurrence[i][c]位置 i 及之后字符 c 首次出现的位置 int[][] nextOccurrence new int[source.length()][26]; // 基础情形最后一行全部置 -1仅记录最后一个字符 for (int c 0; c 26; c) { nextOccurrence[source.length() - 1][c] -1; } nextOccurrence[source.length() - 1][source.charAt(source.length() - 1) - a] source.length() - 1; // 从右往左递推填充 for (int idx source.length() - 2; idx 0; idx--) { for (int c 0; c 26; c) { nextOccurrence[idx][c] nextOccurrence[idx 1][c]; } nextOccurrence[idx][source.charAt(idx) - a] idx; } int sourceIterator 0; int count 1; for (char c : target.toCharArray()) { // 字符不存在于 source不可能 if (nextOccurrence[0][c - a] -1) { return -1; } // 已到 source 末尾或当前位置之后没有该字符回绕并开启新一轮 if (sourceIterator source.length() || nextOccurrence[sourceIterator][c - a] -1) { count; sourceIterator 0; } // O(1) 查询下一出现位置并前进 sourceIterator nextOccurrence[sourceIterator][c - a] 1; } return count; } }impl Solution { pub fn shortest_way(source: String, target: String) - i32 { let src source.as_bytes(); let tgt target.as_bytes(); let source_length src.len(); // next_occurrence[i][c]位置 i 及之后字符 c 首次出现的位置 let mut next_occurrence vec![[-1i32; 26]; source_length]; // 基础情形 next_occurrence[source_length - 1][(src[source_length - 1] - ba) as usize] (source_length - 1) as i32; // 从右往左递推填充 for idx in (0..source_length - 1).rev() { for c in 0..26 { next_occurrence[idx][c] next_occurrence[idx 1][c]; } next_occurrence[idx][(src[idx] - ba) as usize] idx as i32; } let mut source_iterator 0usize; let mut count 1; for c in tgt { let ci (c - ba) as usize; // 字符不存在于 source不可能 if next_occurrence[0][ci] -1 { return -1; } // 已到 source 末尾或当前位置之后没有该字符回绕并开启新一轮 if source_iterator source_length || next_occurrence[source_iterator][ci] -1 { count 1; source_iterator 0; } // O(1) 查询下一出现位置并前进 source_iterator next_occurrence[source_iterator][ci] as usize 1; } count } }复杂度分析时间复杂度O(S T)。建表耗时 O(26·S) O(S)匹配阶段每个字符一次 O(1) 查询共 O(T)。空间复杂度O(S)nextOccurrence表的大小为 S × 26即 O(S)。其中 S 是source的长度T 是target的长度。四种解法对比一览解法核心思想时间复杂度空间复杂度适用场景解法一逐份拼接真拼接 子序列判定O(T²·S)O(T·S)代码最直观适合讲解与教学验证解法二双指针取模环形扫描虚拟拼接O(S·T)O(1)空间最优面试常考手写版本解法三倒排索引 二分位置列表 lower_boundO(S T·log S)O(S)source 很长、target 较长时的均衡选择解法四2D 表预计算下一出现位置O(S T)O(S)查询最速适合大规模数据与复用场景从工程视角看解法四是预计算换时间的典型范式只要source固定不变nextOccurrence表可以反复用于多个target的查询而解法二的 O(1) 空间在source、target都很长且内存受限时更值得优先考虑。常见陷阱Common Pitfalls1. 忘记检查不可能字符动手匹配之前必须先验证target的每个字符都存在于source。只要有一个字符缺失无论拼接多少份source都不可能形成target此时必须返回-1。跳过这一步会导致无限循环如解法一或错误答案如解法二、三、四中数组越界/空列表访问。这是全部四种解法共用的第一道校验务必放在匹配循环之前。2. 回绕 source 时的越界与 off-by-one用指针跟踪source位置时最常见的错误是回绕逻辑处理不当到达source末尾仍未找到所需字符时必须重置回开头并且把计数加一。典型的失误包括回绕时忘记递增count导致结果偏小指针重置位置错误例如重置为0后没有加一或直接复用越界下标导致后续访问越界取模运算写错例如用sourceIterator 1而没有取模造成下标溢出。3. 子序列计数方式错误count的语义是完整扫描source的轮数应当在每次开启新一轮扫描时递增而不是每匹配一个字符就递增一次。常见错误初始化count 0而不是count 1解法一、三、四从第一份拷贝就算一轮起点必须是 1在循环内错误的位置递增计数导致最终答案 off-by-one解法二中把命中字符后的前进误写成命中即计数导致每个字符都被计一轮。建议写完后用source abc、target abcbc答案 2以及source abc、target acdbc答案 -1这类小用例自测回绕与不可能分支。延伸阅读本文核心来源articles/shortest-way-to-form-string.md内含全部 10 语言Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust的完整 tabs 版实现子序列基础概念is-subsequence.md子序列与 DP 进阶longest-common-subsequence.md二分查找模板binary-search.md文章撰写规范复杂度必须标注、尽量覆盖全部解法articles/README.md。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 1055 Shortest Way to Form String 四种解法全解析：子序列判定、双指针、倒排索引与 2D 下一出现位置表
LeetCode 1055 Shortest Way to Form String 四种解法全解析子序列判定、双指针、倒排索引与 2D 下一出现位置表【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 articles/shortest-way-to-form-string.md 为核心骨架系统讲解如何计算将字符串target作为子序列拼出所需的最少source拷贝份数。文章依次给出暴力拼接、双指针模拟、倒排索引 二分查找、2D 预计算表四种思路并配套多语言实现、复杂度对比与常见陷阱分析。读完你不仅能 AC 该题还能把子序列判定 循环扫描 跳表加速这一套方法论迁移到其他字符串与贪心匹配场景。前置知识在动手之前请确保你对以下四个基础概念足够熟悉它们是理解全部四种解法的地基子序列Subsequence理解一个字符串是另一个字符串的子序列意味着什么——不要求连续只要求按相对顺序出现。可参考仓库内 is-subsequence.md 与 longest-common-subsequence.md 两篇文章加深理解。双指针技巧Two Pointers用两个指针分别遍历、比较两个字符串线性完成匹配是解法一与解法二的核心工具。二分查找Binary Search在有序数组中快速定位元素用于解法三中对下一出现位置的 O(log S) 查询。预计算 / 动态规划Precomputation / DP预先构建查找表使匹配阶段对下一个字符位置的查询降到 O(1)这是解法四的本质。问题定义与题目理解本题的目标是给定两个字符串source和target返回使得target成为source重复拼接若干次后所得字符串的子序列所需的最少拷贝次数若无论如何拼接都不可能即target中存在source没有的字符返回-1。关键点在于拼接次数从1起步——单个source本身就是拼接一次子序列而非子串因此每份拷贝之间不要求字符连续跨拷贝匹配是允许的不可能情形唯一判定条件target中存在某个字符在source中从未出现。一旦判定不可能直接返回-1这是所有解法共用的第一道关卡。根据仓库内 articles/README.md 的规范每篇文章应当覆盖 NeetCode 视频中尽可能全的解法并给出时间/空间复杂度本文即按此标准组织四种递进式解法。解法一逐份拼接直到 target 成为子序列Concatenate until Subsequence直觉Intuition最直白、最符合题目字面描述的思路既然答案就是需要拼接多少份source那就真的去拼接。先把source里的字符放进一个集合逐一检查target的每个字符一旦发现缺失字符立刻返回-1。随后从concatenatedSource source、count 1开始每轮判断target是否已是拼接串的子序列不是就再追加一份source并把count加一直到满足条件为止。算法步骤Algorithm构建source中所有字符的集合用布尔数组亦可遍历target每个字符若任一字符不在集合中返回-1初始化concatenatedSource sourcecount 1循环只要target还不是concatenatedSource的子序列向concatenatedSource追加一份sourcecount 1返回count。代码实现class Solution: def shortestWay(self, source: str, target: str) - int: # 判断 to_check 是否为 in_string 的子序列 def is_subsequence(to_check, in_string): i j 0 while i len(to_check) and j len(in_string): if to_check[i] in_string[j]: i 1 j 1 return i len(to_check) # source 中所有字符的集合也可用布尔数组 source_chars set(source) # 检查 target 的每个字符是否都存在于 source缺一即返回 -1 for char in target: if char not in source_chars: return -1 # 逐份拼接 source直到 target 成为拼接串的子序列 concatenated_source source count 1 while not is_subsequence(target, concatenated_source): concatenated_source source count 1 return countclass Solution { public: int shortestWay(string source, string target) { // 布尔数组标记 source 中出现过的字符 bool sourceChars[26] {false}; for (char c : source) sourceChars[c - a] true; // 任一 target 字符缺失则不可能返回 -1 for (char c : target) { if (!sourceChars[c - a]) return -1; } // 拼接直到 target 是拼接串的子序列 string concatenatedSource source; int count 1; while (!isSubsequence(target, concatenatedSource)) { concatenatedSource source; count; } return count; } // 判断 toCheck 是否为 inString 的子序列 bool isSubsequence(string toCheck, string inString) { int i 0, j 0; while (i toCheck.length() j inString.length()) { if (toCheck[i] inString[j]) i; j; } return i toCheck.length(); } };func shortestWay(source string, target string) int { // 布尔数组标记 source 中出现过的字符 sourceChars : make([]bool, 26) for _, c : range source { sourceChars[c-a] true } // 任一 target 字符缺失则不可能返回 -1 for _, c : range target { if !sourceChars[c-a] { return -1 } } // 判断 toCheck 是否为 inString 的子序列 isSubsequence : func(toCheck, inString string) bool { i, j : 0, 0 for i len(toCheck) j len(inString) { if toCheck[i] inString[j] { i } j } return i len(toCheck) } // 拼接直到 target 成为拼接串的子序列 concatenatedSource : source count : 1 for !isSubsequence(target, concatenatedSource) { concatenatedSource source count } return count }其余语言Java、JavaScript、C#、Kotlin、Swift、Rust的实现与上述结构完全一致先做字符存在性检查再用双指针子序列判定 循环拼接可参考原文档 articles/shortest-way-to-form-string.md 中的完整 tabs 版本。复杂度分析时间复杂度O(T² · S)其中 S 为source长度、T 为target长度。最坏情况下每次追加一份source都要重新做一次 O(S·T) 的子序列判定而最多需要拼接 T 次target中每个字符都要消耗一整份拷贝时达到上界故总体约为 O(T · (S·T)) O(T²·S)。空间复杂度O(T·S)因为最坏情况下concatenatedSource的长度会膨胀到 T·S。其中 S 是source的长度T 是target的长度。解法二双指针循环扫描Two Pointers直觉Intuition解法一反复拼接出巨大字符串的做法既浪费内存又重复计算。解法二改为模拟同一过程用单个指针sourceIterator在source上线性移动配合取模运算把source当作环形字符串来虚拟拼接。每次需要找target的某个字符时就向前推进sourceIterator直到命中当指针因取模回到开头0说明进入新一轮扫描此时count加一。整个过程无需真正拼接任何字符串。算法步骤Algorithm构建source的字符集合target中任一字符缺失则返回-1初始化sourceIterator 0、count 0遍历target每个字符若sourceIterator 0说明即将开始一轮新的扫描count 1当source[sourceIterator]不等于当前字符时用sourceIterator (sourceIterator 1) % m前进若前进后回到0count 1命中当前字符后sourceIterator (sourceIterator 1) % m再前进一位为匹配下一个字符做准备返回count。代码实现class Solution: def shortestWay(self, source: str, target: str) - int: # source 中所有字符的集合也可用布尔数组 source_chars set(source) # 检查 target 的每个字符是否都存在于 source for char in target: if char not in source_chars: return -1 # source 长度用于取模回绕到开头 m len(source) # source 上的扫描指针 source_iterator 0 # 完整扫描 source 的轮数。当在寻找某个 target 字符的过程中 # source_iterator 再次回到起点时就说明开启了一轮新扫描。 count 0 for char in target: # 指针在起点即将开始新一轮扫描 if source_iterator 0: count 1 # 线性扫描 source直到找到当前字符 while source[source_iterator] ! char: # 取模前进实现环形回绕 source_iterator (source_iterator 1) % m # 回绕到起点说明开启新的一轮 if source_iterator 0: count 1 # 找到字符后前进一位注意此时不要立刻增加 count # 因为还不确定 target 是否还有剩余字符。 source_iterator (source_iterator 1) % m return countclass Solution { public: int shortestWay(string source, string target) { // 布尔数组标记 source 中出现过的字符 bool sourceChars[26] {false}; for (char c : source) sourceChars[c - a] true; // 任一 target 字符缺失则不可能 for (char c : target) { if (!sourceChars[c - a]) return -1; } int m source.length(); // 用于取模回绕 int sourceIterator 0; // source 扫描指针 int count 0; // 完整扫描轮数 for (char c : target) { if (sourceIterator 0) count; // 开启新一轮 while (source[sourceIterator] ! c) { // 线性查找 sourceIterator (sourceIterator 1) % m; if (sourceIterator 0) count; // 回绕计一轮 } sourceIterator (sourceIterator 1) % m; // 命中后前进 } return count; } };class Solution { shortestWay(source, target) { // 布尔数组标记 source 中出现过的字符 let sourceChars new Array(26).fill(false); for (let c of source) { sourceChars[c.charCodeAt(0) - a.charCodeAt(0)] true; } // 任一 target 字符缺失则不可能 for (let c of target) { if (!sourceChars[c.charCodeAt(0) - a.charCodeAt(0)]) { return -1; } } let m source.length; // 用于取模回绕 let sourceIterator 0; // source 扫描指针 let count 0; // 完整扫描轮数 for (let c of target) { if (sourceIterator 0) count; // 开启新一轮 while (source[sourceIterator] ! c) { // 线性查找 sourceIterator (sourceIterator 1) % m; if (sourceIterator 0) count; // 回绕计一轮 } sourceIterator (sourceIterator 1) % m; // 命中后前进 } return count; } }复杂度分析时间复杂度O(S·T)。对target的每个字符最坏情况下指针要在source上绕一整圈S 步才能命中故总量级为 O(S·T)。虽然表面上比解法一更差或持平但它省去了拼接与重复判定实际常数更小且空间占用恒为 O(1)。空间复杂度O(1)只用了常数个变量。其中 S 是source的长度T 是target的长度。解法三倒排索引 二分查找Inverted Index and Binary Search直觉Intuition解法二对target的每个字符都可能线性扫过整个source仍有冗余。解法三通过预计算倒排索引把找下一个位置变成二分查找先为source中每种字符维护一个升序排列的下标列表。匹配target的字符 c 时只需在charToIndices[c]中用二分查找定位第一个 sourceIterator的下标若列表已耗尽越界说明这一轮扫描找不到需要回绕到开头、开启新的一轮。算法步骤Algorithm构建倒排索引对source中每个字符存一个按升序排列的位置列表charToIndices[c]初始化sourceIterator 0、count 1遍历target每个字符若charToIndices[c]为空字符不存在返回-1在charToIndices[c]中二分查找第一个 sourceIterator的下标若查找结果越界所有出现位置都已越过count 1并取列表第一个位置indices[0] 1作为新的sourceIterator否则取indices[index] 1返回count。代码实现class Solution { public int shortestWay(String source, String target) { // 每种字符在 source 中的下标列表 ArrayListInteger[] charToIndices new ArrayList[26]; for (int i 0; i source.length(); i) { char c source.charAt(i); if (charToIndices[c - a] null) { charToIndices[c - a] new ArrayList(); } charToIndices[c - a].add(i); } int sourceIterator 0; // source 扫描指针 int count 1; // 需要的完整扫描轮数 for (char c : target.toCharArray()) { // 字符不在 source 中不可能 if (charToIndices[c - a] null) { return -1; } // 二分查找第一个 sourceIterator 的下标 ArrayListInteger indices charToIndices[c - a]; int index Collections.binarySearch(indices, sourceIterator); // 未命中时binarySearch 返回 -(插入点)-1还原为插入点 if (index 0) { index -index - 1; } // 插入点在列表末尾本轮找不到开启新一轮 if (index indices.size()) { count; sourceIterator indices.get(0) 1; } else { sourceIterator indices.get(index) 1; } } return count; } }class Solution { public: int shortestWay(string source, string target) { // 每种字符在 source 中的下标列表 vectorint charToIndices[26]; for (int i 0; i source.size(); i) { charToIndices[source[i] - a].push_back(i); } int sourceIterator 0; // source 扫描指针 int count 1; // 需要的完整扫描轮数 for (int i 0; i target.size(); i) { // 字符不在 source 中不可能 if (charToIndices[target[i] - a].size() 0) { return -1; } // lower_bound 找第一个 sourceIterator 的位置 vectorint indices charToIndices[target[i] - a]; int index lower_bound(indices.begin(), indices.end(), sourceIterator) - indices.begin(); // 越界本轮找不到开启新一轮 if (index indices.size()) { count; sourceIterator indices[0] 1; } else { sourceIterator indices[index] 1; } } return count; } };class Solution: def shortestWay(self, source: str, target: str) - int: # 每种字符在 source 中的下标列表 char_to_indices [[] for _ in range(26)] for i, c in enumerate(source): char_to_indices[ord(c) - ord(a)].append(i) # 自定义二分查找返回第一个 target 的下标无则返回 len(arr) def lower_bound(arr, target): left, right 0, len(arr) while left right: mid (left right) // 2 if arr[mid] target: left mid 1 else: right mid return left source_iterator 0 # source 扫描指针 count 1 # 需要的完整扫描轮数 for c in target: idx ord(c) - ord(a) # 字符不在 source 中不可能 if not char_to_indices[idx]: return -1 indices char_to_indices[idx] pos lower_bound(indices, source_iterator) # 越界本轮找不到开启新一轮 if pos len(indices): count 1 source_iterator indices[0] 1 else: source_iterator indices[pos] 1 return count复杂度分析时间复杂度O(S T·log S)。建索引耗时 O(S)匹配阶段每个字符一次二分查找耗时 O(log S)共 T 次。空间复杂度O(S)用于存储所有字符的位置列表。其中 S 是source的长度T 是target的长度。解法四2D 数组预计算下一出现位置2D Array / Next Occurrence Table直觉Intuition解法三的二分查找已经很快但还可以把查询压缩到 O(1)预计算一个二维表nextOccurrence[i][c]表示source中位置 i 及其之后字符 c 第一次出现的位置。该表从右往左用递推关系填充本质是动态规划每一行先复制下一行的全部值再把当前位置字符的条目更新为当前位置。匹配阶段每次查询都是 O(1) 的数组访问匹配完成后总复杂度只有 O(S T)。算法步骤Algorithm创建nextOccurrence尺寸为source.length × 26初始化最后一行全部置为-1再把source最后一个字符对应的条目设为source.length - 1从右往左填充其余行把nextOccurrence[i1]的值整体复制到nextOccurrence[i]更新nextOccurrence[i][source[i]] i初始化sourceIterator 0、count 1遍历target每个字符 c若nextOccurrence[0][c] -1说明 c 在source中不存在返回-1若sourceIterator source.length或nextOccurrence[sourceIterator][c] -1当前位置之后没有 c 了count 1并把sourceIterator重置为0令sourceIterator nextOccurrence[sourceIterator][c] 1返回count。代码实现class Solution: def shortestWay(self, source: str, target: str) - int: source_length len(source) # next_occurrence[i][c]source 在位置 i 及之后字符 c 首次出现的位置 next_occurrence [defaultdict(int) for idx in range(source_length)] # 基础情形最后一行只记录最后一个字符 next_occurrence[source_length - 1][source[source_length - 1]] source_length - 1 # 从右往左递推填充 for idx in range(source_length - 2, -1, -1): next_occurrence[idx] next_occurrence[idx 1].copy() next_occurrence[idx][source[idx]] idx source_iterator 0 count 1 for char in target: # 字符不存在于 source不可能 if char not in next_occurrence[0]: return -1 # 已到 source 末尾或当前位置之后没有该字符回绕并开启新一轮 if (source_iterator source_length or char not in next_occurrence[source_iterator]): count 1 source_iterator 0 # O(1) 查询下一出现位置并前进 source_iterator next_occurrence[source_iterator][char] 1 return countclass Solution { public int shortestWay(String source, String target) { // nextOccurrence[i][c]位置 i 及之后字符 c 首次出现的位置 int[][] nextOccurrence new int[source.length()][26]; // 基础情形最后一行全部置 -1仅记录最后一个字符 for (int c 0; c 26; c) { nextOccurrence[source.length() - 1][c] -1; } nextOccurrence[source.length() - 1][source.charAt(source.length() - 1) - a] source.length() - 1; // 从右往左递推填充 for (int idx source.length() - 2; idx 0; idx--) { for (int c 0; c 26; c) { nextOccurrence[idx][c] nextOccurrence[idx 1][c]; } nextOccurrence[idx][source.charAt(idx) - a] idx; } int sourceIterator 0; int count 1; for (char c : target.toCharArray()) { // 字符不存在于 source不可能 if (nextOccurrence[0][c - a] -1) { return -1; } // 已到 source 末尾或当前位置之后没有该字符回绕并开启新一轮 if (sourceIterator source.length() || nextOccurrence[sourceIterator][c - a] -1) { count; sourceIterator 0; } // O(1) 查询下一出现位置并前进 sourceIterator nextOccurrence[sourceIterator][c - a] 1; } return count; } }impl Solution { pub fn shortest_way(source: String, target: String) - i32 { let src source.as_bytes(); let tgt target.as_bytes(); let source_length src.len(); // next_occurrence[i][c]位置 i 及之后字符 c 首次出现的位置 let mut next_occurrence vec![[-1i32; 26]; source_length]; // 基础情形 next_occurrence[source_length - 1][(src[source_length - 1] - ba) as usize] (source_length - 1) as i32; // 从右往左递推填充 for idx in (0..source_length - 1).rev() { for c in 0..26 { next_occurrence[idx][c] next_occurrence[idx 1][c]; } next_occurrence[idx][(src[idx] - ba) as usize] idx as i32; } let mut source_iterator 0usize; let mut count 1; for c in tgt { let ci (c - ba) as usize; // 字符不存在于 source不可能 if next_occurrence[0][ci] -1 { return -1; } // 已到 source 末尾或当前位置之后没有该字符回绕并开启新一轮 if source_iterator source_length || next_occurrence[source_iterator][ci] -1 { count 1; source_iterator 0; } // O(1) 查询下一出现位置并前进 source_iterator next_occurrence[source_iterator][ci] as usize 1; } count } }复杂度分析时间复杂度O(S T)。建表耗时 O(26·S) O(S)匹配阶段每个字符一次 O(1) 查询共 O(T)。空间复杂度O(S)nextOccurrence表的大小为 S × 26即 O(S)。其中 S 是source的长度T 是target的长度。四种解法对比一览解法核心思想时间复杂度空间复杂度适用场景解法一逐份拼接真拼接 子序列判定O(T²·S)O(T·S)代码最直观适合讲解与教学验证解法二双指针取模环形扫描虚拟拼接O(S·T)O(1)空间最优面试常考手写版本解法三倒排索引 二分位置列表 lower_boundO(S T·log S)O(S)source 很长、target 较长时的均衡选择解法四2D 表预计算下一出现位置O(S T)O(S)查询最速适合大规模数据与复用场景从工程视角看解法四是预计算换时间的典型范式只要source固定不变nextOccurrence表可以反复用于多个target的查询而解法二的 O(1) 空间在source、target都很长且内存受限时更值得优先考虑。常见陷阱Common Pitfalls1. 忘记检查不可能字符动手匹配之前必须先验证target的每个字符都存在于source。只要有一个字符缺失无论拼接多少份source都不可能形成target此时必须返回-1。跳过这一步会导致无限循环如解法一或错误答案如解法二、三、四中数组越界/空列表访问。这是全部四种解法共用的第一道校验务必放在匹配循环之前。2. 回绕 source 时的越界与 off-by-one用指针跟踪source位置时最常见的错误是回绕逻辑处理不当到达source末尾仍未找到所需字符时必须重置回开头并且把计数加一。典型的失误包括回绕时忘记递增count导致结果偏小指针重置位置错误例如重置为0后没有加一或直接复用越界下标导致后续访问越界取模运算写错例如用sourceIterator 1而没有取模造成下标溢出。3. 子序列计数方式错误count的语义是完整扫描source的轮数应当在每次开启新一轮扫描时递增而不是每匹配一个字符就递增一次。常见错误初始化count 0而不是count 1解法一、三、四从第一份拷贝就算一轮起点必须是 1在循环内错误的位置递增计数导致最终答案 off-by-one解法二中把命中字符后的前进误写成命中即计数导致每个字符都被计一轮。建议写完后用source abc、target abcbc答案 2以及source abc、target acdbc答案 -1这类小用例自测回绕与不可能分支。延伸阅读本文核心来源articles/shortest-way-to-form-string.md内含全部 10 语言Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust的完整 tabs 版实现子序列基础概念is-subsequence.md子序列与 DP 进阶longest-common-subsequence.md二分查找模板binary-search.md文章撰写规范复杂度必须标注、尽量覆盖全部解法articles/README.md。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考