google 电话面试一面（已获二面）

lchen77

lchen77 发表于 2015-9-23 01:58
嗯，思路确实差不多，不过
for(int i=0; i

万恶的下标，都没有啦。

cbwcs

lchen77 发表于 2015-9-23 02:00
万恶的下标，都没有啦。

是记录不相等的位置的index，只是我打进去的code都没有index了

lchen77

cbwcs 发表于 2015-9-23 02:08
是记录不相等的位置的index，只是我打进去的code都没有index了

嗯，后来为明白啦。
楼主你的代码比为的简洁。
我当时那个code写的那就一个庞大。google doc 又不方便对齐，写的我自己都觉得难看。

hulahu

楼主，给个example麻

purplesky85

cbwcs 发表于 2015-9-23 01:05
vector editdistance(string s, string t)
{
vector ret(2,-1);

你的代码时间复杂度是O(n^2)吧，
比如T ＝ "aaaccc", S = "bbbaaa".

purplesky85

cbwcs 发表于 2015-9-23 01:05
vector editdistance(string s, string t)
{
vector ret(2,-1);

你的代码时间复杂度是O(n^2)吧，
比如T ＝ "aaaccc", S = "bbbaaa".

cbwcs

purplesky85 发表于 2015-9-23 03:48
你的代码时间复杂度是O(n^2)吧，
比如T ＝ "aaaccc", S = "bbbaaa".

对，是O(N^2)

坐看云起

利用好lower case这个条件，应该可以O(1)空间，O(n)时间解决

say543

坐看云起发表于 2015-9-23 04:13
利用好lower case这个条件，应该可以O(1)空间，O(n)时间解决

能说说怎么做吗? 只想得出o(n^2)的方法...

stellari

<div style="font-family: 'Lucida Grande', 'Segoe UI', 'Apple SD Gothic Neo', 'Malgun Gothic', 'Lucida Sans Unicode', Helvetica, Arial, sans-serif; font-size: 0.9em; overflow-x: hidden; overflow-y: auto; margin: 0px !important; padding: 5px 20px 26px !important; background-color: rgb(255, 255, 255);font-family: 'Hiragino Sans GB', 'Microsoft YaHei', STHeiti, SimSun, 'Lucida Grande', 'Lucida Sans Unicode', 'Lucida Sans', 'Segoe UI', AppleSDGothicNeo-Medium, 'Malgun Gothic', Verdana, Tahoma, sans-serif; padding: 20px;padding: 20px; color: rgb(34, 34, 34); font-size: 15px; font-family: 'Roboto Condensed', Tauri, 'Hiragino Sans GB', 'Microsoft YaHei', STHeiti, SimSun, 'Lucida Grande', 'Lucida Sans Unicode', 'Lucida Sans', 'Segoe UI', AppleSDGothicNeo-Medium, 'Malgun Gothic', Verdana, Tahoma, sans-serif; line-height: 1.6; -webkit-font-smoothing: antialiased; background: rgb(255, 255, 255);"><h4 id="我想应该是可以做到o(n)的，只要能够" style="clear: both;font-size: 1.4em; font-weight: bold; margin: 0.99em 0px 0.66em;margin-top: 0px;"><a name="我想应该是可以做到o(n)的，只要能够" href="#我想应该是可以做到o(n)的，只要能够" style="text-decoration: none; vertical-align: baseline;color: rgb(50, 105, 160);"></a>我想应该是可以做到O(N)的，只要能够</h4><p style="margin-top: 0px;margin: 1em 0px; word-wrap: break-word;">抓住字符数<span><span class="MathJax_Preview" style="color: rgb(136, 136, 136);"></span><span class="MathJax" id="MathJax-Element-56-Frame" role="textbox" aria-readonly="true" style="display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px;"><nobr style="border: 0px; padding: 0px; margin: 0px; max-width: 5000em; max-height: 5000em; min-width: 0px; min-height: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;white-space: nowrap !important;-webkit-transition: none; transition: none;"><span class="math" id="MathJax-Span-234" style="width: 3.617em; display: inline-block;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"><span style="display: inline-block; position: relative; width: 2.951em; height: 0px; font-size: 122%;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"><span style="position: absolute; clip: rect(1.848em 1000em 2.864em -0.471em); top: -2.678em; left: 0em;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"><span class="mrow" id="MathJax-Span-235" style="display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"><span class="mi" id="MathJax-Span-236" style="font-family: MathJax_Math; font-style: italic;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;">n</span><span class="mo" id="MathJax-Span-237" style="font-family: MathJax_Main; padding-left: 0.278em;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;">=</span><span class="mn" id="MathJax-Span-238" style="font-family: MathJax_Main; padding-left: 0.278em;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;">26</span></span><span style="display: inline-block; width: 0px; height: 2.678em;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"></span></span></span><span style="border-left-width: 0em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.973em; vertical-align: -0.094em;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-56">n=26</script></span>这个特点。比如开一个26x26的数组</p><pre style="border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; word-wrap: break-word; border: 1px solid rgb(204, 204, 204); overflow: auto; padding: 0.5em;"><code class="c++" data-origin="<pre><code class="c++">int P[26][26]
</code></pre>" style="border: 0px; display: block;font-family: Consolas, Inconsolata, Courier, monospace; font-weight: bold; white-space: pre; margin: 0px;border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; word-wrap: break-word; border: 1px solid rgb(204, 204, 204); padding: 0px 5px; margin: 0px 2px;font-size: 1em; letter-spacing: -1px; font-weight: bold;">int P[26][26]
</code></pre><p style="margin: 1em 0px; word-wrap: break-word;">来储存之前出现的所有s[i],t[i]的组合怎么样？</p></div>

补充内容 (2015-9-23 17:41):
。。。不好意思，我不小心把整段HTML代码粘贴进来了。能否请版主删除此楼？