React递归实现嵌套片段包裹的算法问题求助

I have two datasets:

• snippets: An array of time-range based segments that may overlap or nest inside each other
• words: An array of timed words that need to be wrapped in <Snippet> components if they fall within any snippet's time range

Input Data #

const snippets = [
  { start: 48.12, end: 50.8, id: 12, snippetTitle: "This is the title" },
  { start: 48.29, end: 49.1, id: 13, snippetTitle: "This is the title" }
];
let words = [
  {"word":" yeah","start_time":"46.44","end_time":"46.82","__typename":"SimplifiedWord"},
  {"word":".","start_time":"46.44","end_time":"46.82","__typename":"SimplifiedWord"},
  {"word":" So","start_time":"47.55","end_time":"47.81","__typename":"SimplifiedWord"},
  {"word":" now","start_time":"47.82","end_time":"48.12","__typename":"SimplifiedWord"},
  {"word":" it","start_time":"48.12","end_time":"48.28","__typename":"SimplifiedWord"},
  {"word":" works","start_time":"48.29","end_time":"48.74","__typename":"SimplifiedWord"},
  {"word":" for","start_time":"48.75","end_time":"49.1","__typename":"SimplifiedWord"},
  {"word":" for","start_time":"49.11","end_time":"49.67","__typename":"SimplifiedWord"},
  {"word":" to","start_time":"49.68","end_time":"50.23","__typename":"SimplifiedWord"},
  {"word":" let","start_time":"50.33","end_time":"50.62","__typename":"SimplifiedWord"},
  {"word":" me","start_time":"50.62","end_time":"50.8","__typename":"SimplifiedWord"},
  {"word":" refresh","start_time":"50.8","end_time":"51.41","__typename":"SimplifiedWord"},
  {"word":" the","start_time":"51.42","end_time":"51.72","__typename":"SimplifiedWord"},
  {"word":" computer","start_time":"51.73","end_time":"52.55","__typename":"SimplifiedWord"},
  {"word":".","start_time":"51.73","end_time":"52.55","__typename":"SimplifiedWord"}
];

Current Limitation #

My existing reduce approach only handles single-level wrapping and can't properly manage nested/overlapping snippets:

let x = words.reduce((accumulator, currentValue, idx) => {
  let isin = isInSnippets(currentValue);
  if (!isin) {
    if (cache.length > 0) {
      accumulator.push(
        <Snippet className="wrapit" key={idx}>
          <TextContent words={cache} skip identity={identity} ></TextContent>
        </Snippet>
      );
      cache = [];
    }
    accumulator.push(
      <span key={`${currentValue.word}${idx}`} data-start={currentValue.start_time} data-end={currentValue.end_time} data-idnt={identity} >
        {currentValue.word}
      </span>
    );
  } else cache.push(currentValue);
  return accumulator;
}, []);

Desired Output #

I need a nested JSX structure where inner snippets are wrapped inside outer ones, like this:

<span data-start="46.44" data-end="46.82"> yeah</span>
<span data-start="46.44" data-end="46.82">.</span>
<span data-start="47.55" data-end="47.81"> So</span>
<span data-start="47.82" data-end="48.12"> now</span>
<Snippet>
  <span data-start="48.12" data-end="48.28"> it</span>
  <Snippet>
    <span data-start="48.29" data-end="48.74"> works</span>
    <span data-start="48.75" data-end="49.1"> for</span>
  </Snippet>
  <span data-start="49.11" data-end="49.67"> for</span>
  <span data-start="49.68" data-end="50.23"> to</span>
  <span data-start="50.33" data-end="50.62"> let</span>
  <span data-start="50.62" data-end="50.8"> me</span>
</Snippet>
<span data-start="50.8" data-end="51.41"> refresh</span>
<span data-start="51.42" data-end="51.72"> the</span>
<span data-start="51.73" data-end="52.55"> computer</span>
<span data-start="51.73" data-end="52.55">.</span>

To handle nested/overlapping snippets, we'll break this into three key steps:

1. Preprocess snippets into a nested tree structure to clearly define parent-child relationships
2. Group consecutive words by their snippet membership to avoid redundant wrapping
3. **Recursively wrap word groups in the appropriate nested <Snippet> components

Step 1: Build a Nested Snippet Tree #

First, we sort snippets and construct a tree where each parent snippet contains its nested child snippets:

// Sort snippets: start time ascending, end time descending (ensures outer snippets come first)
const sortedSnippets = [...snippets].sort((a, b) => {
  if (a.start !== b.start) return a.start - b.start;
  return b.end - a.end;
});

// Build a nested tree structure of snippets
const buildSnippetTree = (snippets) => {
  const tree = [];
  const stack = [];

  for (const snippet of snippets) {
    // Remove non-parent snippets from the stack
    while (stack.length > 0 && stack[stack.length - 1].end < snippet.end) {
      stack.pop();
    }

    // Add snippet to tree or as a child of the current parent
    if (stack.length === 0) {
      tree.push(snippet);
    } else {
      stack[stack.length - 1].children = stack[stack.length - 1].children || [];
      stack[stack.length - 1].children.push(snippet);
    }

    stack.push(snippet);
  }

  return tree;
};

const snippetTree = buildSnippetTree(sortedSnippets);

Step 2: Helper Functions #

We need utility functions to check snippet membership and recursively wrap elements:

// Check if a word falls entirely within a snippet's time range
const isWordInSnippet = (word, snippet) => {
  const wordStart = parseFloat(word.start_time);
  const wordEnd = parseFloat(word.end_time);
  return wordStart >= snippet.start && wordEnd <= snippet.end;
};

// Get all snippets that contain a word, ordered from outer to inner
const getContainingSnippets = (word, snippetTree) => {
  const matchingSnippets = [];

  const traverseTree = (node) => {
    if (isWordInSnippet(word, node)) {
      matchingSnippets.push(node);
      if (node.children) {
        node.children.forEach(child => traverseTree(child));
      }
    }
  };

  snippetTree.forEach(node => traverseTree(node));
  return matchingSnippets;
};

// Recursively wrap an element in nested Snippet components
const wrapWithSnippets = (element, snippets) => {
  if (snippets.length === 0) return element;
  const [outerSnippet, ...innerSnippets] = snippets;
  
  return (
    <Snippet key={outerSnippet.id} className="wrapit">
      {wrapWithSnippets(element, innerSnippets)}
    </Snippet>
  );
};

Step 3: Group Words and Generate Render Output #

Finally, we group consecutive words with the same snippet membership and generate the nested JSX:

// Group consecutive words that belong to the same set of snippets
const groupWordsBySnippets = (words, snippetTree) => {
  const groups = [];
  let currentGroup = { words: [], snippets: [] };

  for (const word of words) {
    const wordSnippets = getContainingSnippets(word, snippetTree);
    // Compare snippet IDs to check if we're in the same group
    const currentSnippetIds = currentGroup.snippets.map(s => s.id);
    const wordSnippetIds = wordSnippets.map(s => s.id);
    
    const isSameGroup = JSON.stringify(currentSnippetIds) === JSON.stringify(wordSnippetIds);

    if (!isSameGroup && currentGroup.words.length > 0) {
      groups.push(currentGroup);
      currentGroup = { words: [word], snippets: wordSnippets };
    } else {
      currentGroup.words.push(word);
      if (currentGroup.snippets.length === 0) {
        currentGroup.snippets = wordSnippets;
      }
    }
  }

  if (currentGroup.words.length > 0) {
    groups.push(currentGroup);
  }

  return groups;
};

// Generate the final array of JSX elements
const renderElements = groupWordsBySnippets(words, snippetTree).map((group, idx) => {
  // Create the base element: either TextContent or individual spans
  const baseElement = group.snippets.length > 0 ? (
    <TextContent 
      key={`text-group-${idx}`} 
      words={group.words} 
      skip 
      identity={identity}
    />
  ) : (
    group.words.map((word, wordIdx) => (
      <span 
        key={`word-${idx}-${wordIdx}`} 
        data-start={word.start_time} 
        data-end={word.end_time} 
        data-idnt={identity}
      >
        {word.word}
      </span>
    ))
  );

  return wrapWithSnippets(baseElement, group.snippets);
});

How This Works #

• The snippet tree ensures we always wrap outer snippets first, then inner ones
• Grouping consecutive words reduces unnecessary <Snippet> components and keeps the DOM clean
• Recursive wrapping dynamically handles any depth of nested/overlapping snippets, no matter how complex the structure gets

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