阿里巴巴面试题：字符串最少空格分割（代码打印问题求助）

Hey there! Let's work through this Alibaba interview problem together. Your goal is to split the string into dictionary words with the least number of spaces (which is equivalent to finding the split with the fewest words, since spaces = word count - 1).

First, let's diagnose why your current code isn't working as expected:

• Your recursive function rec is creating nested arrays instead of flat lists of words, which breaks the printing logic.
• The logic for tracking and selecting the minimal-space split isn't properly connected to the recursive results.

Fixing Your Recursive Approach #

Let's adjust the recursive function to return all valid splits, then pick the one with the fewest words. Here's the revised code:

// Check if a word is a prefix of the current string
function isStartSub(word, str) {
  return str.startsWith(word);
}

// Get the remaining string after removing the prefix word
function getRestStr(word, str) {
  return str.slice(word.length);
}

// Recursively find all valid splits of the string
function findAllSplits(str, dict) {
  if (str.length === 0) {
    return [[]]; // Base case: empty string has one split (empty list)
  }
  
  const splits = [];
  for (const word of dict) {
    if (isStartSub(word, str)) {
      const restStr = getRestStr(word, str);
      // Get all splits for the remaining string, then prepend the current word
      const restSplits = findAllSplits(restStr, dict);
      for (const split of restSplits) {
        splits.push([word, ...split]);
      }
    }
  }
  return splits;
}

// Find the split with the least number of words (i.e., least spaces)
function getMinSpaceSplit(str, dict) {
  const allSplits = findAllSplits(str, dict);
  if (allSplits.length === 0) return null; // No valid split
  
  // Sort splits by word count (ascending) and pick the first one
  return allSplits.sort((a, b) => a.length - b.length)[0];
}

// Print the split as a space-separated string
function printSplit(split) {
  return split.join(' ');
}

// Test the code
const s = "ilikealibaba";
const d = ["i", "like", "ali", "liba", "baba", "alibaba"];
const bestSplit = getMinSpaceSplit(s, d);
console.log(printSplit(bestSplit)); // Output: "i like alibaba"

Key Improvements: #

• findAllSplits returns a list of flat word arrays (no nested mess) instead of modifying a buffer.
• getMinSpaceSplit sorts all valid splits by word count (fewer words = fewer spaces) and selects the optimal one.
• The printing logic is straightforward with join(' ').

Optimized Dynamic Programming Approach #

For longer strings, the recursive approach can be inefficient due to repeated calculations. A dynamic programming (DP) approach is better—it directly tracks the minimal split as we build up the solution:

function minSpaceSplit(str, dict) {
  const n = str.length;
  // dp[i] will store the minimal split for substring str[0..i-1]
  const dp = new Array(n + 1).fill(null);
  dp[0] = []; // Empty string has an empty split
  
  for (let i = 1; i <= n; i++) {
    for (const word of dict) {
      const wordLen = word.length;
      // Check if the word fits at the end of str[0..i-1]
      if (i >= wordLen && str.slice(i - wordLen, i) === word) {
        const prevSplit = dp[i - wordLen];
        if (prevSplit !== null) {
          // If this split is better (fewer words) than current dp[i], update it
          const currentSplit = [...prevSplit, word];
          if (dp[i] === null || currentSplit.length < dp[i].length) {
            dp[i] = currentSplit;
          }
        }
      }
    }
  }
  
  return dp[n];
}

// Test
const s = "ilikealibaba";
const d = ["i", "like", "ali", "liba", "baba", "alibaba"];
const bestSplitDP = minSpaceSplit(s, d);
console.log(bestSplitDP.join(' ')); // Output: "i like alibaba"

Why This Is Better: #

• Efficiency: Avoids redundant recursive calls by reusing previously computed results.
• Direct Optimization: We only keep the minimal split (fewest words) for each substring, so we don't need to generate all splits first.

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