阿里电面题：输出给定字符串的全部连续子串

2019-04-14 12:22发布

站内文章 / 模拟电子
12634 0 1426
时间：2014.03.15 地点：基地二楼 -----------------------------------------------------------------------------

一、问题描述

  刚刚在网上看到一道阿里电面题：输出给定字串的全部连续子串。比如对给给定字符串 “abcd"，应该打印出：a，b，c，d，ab，bc，cd，abc，bcd，abcd等。

-----------------------------------------------

二、解决方案

  也没想太多，找了一种复杂度为O(n*n)的方法，是否有更好的办法呢，但也网上查了查，也没找到，如果有大家可贴出来学习下。我的办法只是遍历字符串中的每一个元素，针对每个元素把以这个元素开头的子字符串都打印出来，实现如下： void PrintAllSubStr(const string& str){ //Postcondition: Print given string's all substrings unsigned str_length = str.length(); for (auto cursor = str.begin(); cursor != str.end();++cursor){ string temp_str(""); for (auto it = cursor; it != str.end(); ++it){ temp_str += *it; cout << temp_str << endl; } } } -----------------------------------------------------------------------------

三、引申

类似的有百度题 打印一个数组中元素的所有组合。 现在发现上面这种方法确实是最高效的，原因之一是充分利用已有的字串，即使得前一字串是后一字串的前缀。
 比如当前打印了a，下一个ab则利用已有的结果a，再下一个结果abc利用已有的结果ab......从而实现O(n*n)的效率。

热门文章