求查找List中拆分目标字符串起止位置的算法

核心思路 #

遍历List的每个元素作为潜在起始点，逐步拼接后续元素，直到匹配目标字符串或确定无法匹配，最终记录起止索引。

具体步骤 #

• 先做边界校验：如果List为空、目标字符串为空，直接返回无匹配。
• 遍历List的每个索引startIdx：
  1. 把当前元素作为初始拼接字符串，检查是否直接匹配目标——如果是，起止索引都是startIdx，直接返回结果。
  2. 如果当前元素是目标的前缀，继续遍历后续索引endIdx，把后续元素拼接到当前字符串后：
     • 每次拼接后，检查是否完全匹配目标：匹配成功则返回startIdx和endIdx。
     • 如果拼接后的字符串长度超过目标，或者目标不再是它的前缀，直接终止这个起始点的后续遍历，换下一个起始点。
• 遍历结束后仍无匹配，返回无匹配标识（比如[-1, -1]）。

Java 实现示例 #

import java.util.List;

public class TargetPositionFinder {
    public static int[] locateTarget(List<String> strList, String target) {
        // 边界情况处理
        if (strList == null || strList.isEmpty() || target == null || target.isBlank()) {
            return new int[]{-1, -1};
        }

        int targetLen = target.length();
        int listSize = strList.size();

        for (int start = 0; start < listSize; start++) {
            StringBuilder current = new StringBuilder(strList.get(start));
            String currentStr = current.toString();

            // 单个元素直接匹配
            if (currentStr.equals(target)) {
                return new int[]{start, start};
            }

            // 当前元素是目标前缀，继续拼接后续元素
            if (target.startsWith(currentStr)) {
                for (int end = start + 1; end < listSize; end++) {
                    current.append(strList.get(end));
                    currentStr = current.toString();

                    // 完全匹配目标
                    if (currentStr.equals(target)) {
                        return new int[]{start, end};
                    }

                    // 长度超了或者不再是前缀，终止循环
                    if (currentStr.length() > targetLen || !target.startsWith(currentStr)) {
                        break;
                    }
                }
            }
        }

        // 无匹配结果
        return new int[]{-1, -1};
    }
}

关键细节 #

• 用StringBuilder拼接字符串，避免频繁创建字符串对象，提升效率。
• 提前终止无效遍历：一旦拼接后的字符串长度超过目标，或者目标不再是它的前缀，就停止后续拼接，减少不必要的计算。
• 覆盖了三种场景：目标在单个元素中、目标跨多个元素、无匹配。

内容的提问来源于stack exchange，提问作者Furqan Ahmed