一道断词面试题

文章目录

这是面试时遇到的一道题，与大家分享。

题目是这样的：

提供一个借口`dictionary(str)`：这个借口可以判断`str`是否为一个单词，如果是一个单词这返回`true`，否则返回`false`。
现在需要借助这个借口写一个函数`f(longStr)`：判断这个`longStr`是否可以被完整地分割成单词，即`longStr`由`dictionary(str)`判断为`true`的单词组成，且最后没有多余的字符。

下面给出我的思路：

我们可以递归调用这个函数`f`，如果第`longStr`的前`n`个字符被`dictionary()`判断为单词，则用`longStr`的剩余字符串调用接口`dictionary()`，直到剩余的字符串长度为0，其中`n`从1开始递增。

给出我的程序：

function f ( longStr) {
	var n = 1;
	var flag = false;
	while ( ! flag && n < longStr.length ){
		if ( dictionary ( longStr.substring(0,n) )) {
		// 如果前n个字符是个单词则递归调用函数f
			flag = f( substring(n) );
		}else {
		// 否则n自增
			n++;
		}
	}
	if ( flag || dictionary( longStr.substring(0,n) ) {
	// dictionary ( longStr.substring(0,n) 判断整个longStr是否是个单词
		return true;
	} else {
		return false;
	}
}