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

国内小哥，人很好，上来啥也没说，直接上题目：

Given two string S and T with same length, the distance is defined as the number of positions in which S and T have different characters. Your task is to

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

所以最后只做了一道题。

感觉面的不是很好，可能是国内小哥帮忙，最后还是给了二面，感恩中！

求大米！

不要说话 发表于 2015-9-23 22:33

其实对于定长的character set来说，这解法已经可以称O(1)内存了。single可以用一个int[26]代替，而location也可以用int[26][26]代替。

case 1: swap distance - 2
case 2: swap distance -1
case 3: swao no use, do not need to swap
我当时是用两个map<char, vector<int>> one for S, one for T,  when S[i] != T[i], save both
然后对于scan map for s， 寻找T中是否有 best case，就是 swap 可以使得 distance － 2，
如果上述 scan 没有找到 best case 但是map T中有另外一个可以被换过来使得当前的S［i］ ＝＝ T[i]，那就 是 case 2， swap 可以使得 distance －1，
如果 上面两种情况都没有找到，那就是说，swap 没有作用，甚至swap会增加 distance，所以就不swap
在处理case 1 的时候， 可以记录找到的case2，因为case 2 是case 1 的必须条件，

<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=&quot;c++&quot;>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代码粘贴进来了。能否请版主删除此楼？

楼主你是怎么做的？我觉得貌似只有暴力搜索或者用很大的空间存贮位置。。。

how to solve it?

for(int i = 0; i < size();i++){
for(int j = i + 1; j < size(); j++)
{
    swap(a[i], a[j]);
}
}

这样O(n^2)  每次 swap , 只能减少2，1，0， -1， -2是这样吗？

vector<int> editdistance(string s, string t)
{
        vector<int> ret(2,-1);
        vector<vector<int>> hash(26,vector<int>());
        for(int i=0; i<s.size(); i++)
        {
                hash[s[i]-'a'].push_back(i);
        }
        for(int i=0; i<t.size();i++)
        {
                if(s[i]!=t[i]&&hash[t[i]-'a'].size()>0)
                {
                        for(auto index:hash[t[i]-'a'])
                        {
                                ret[0]=i;
                                ret[1]=index;
                                if(t[index]==s[i]) return ret;
                        }
                }
        }
        return ret;
}

补充内容 (2015-9-23 01:08):
这个应该是O(N),虽然下面有两个for嵌套，但只可能比较N次。

补充内容 (2015-9-23 01:09):
好像也不对啊！

楼主牛逼 感谢分享

Augustus 发表于 2015-9-23 00:47
楼主你是怎么做的？我觉得貌似只有暴力搜索或者用很大的空间存贮位置。。。

已回复在楼下

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

统一回复在楼下

lchen77 发表于 2015-9-23 01:49
case 1: swap distance - 2
case 2: swap distance -1
case 3: swao no use, do not need to swap

楼主，我的想法跟你基本一致，但不需要用到map,开个数组就好，因为都是lowcase的。
然后只需要记录S的char就好，然后从T开始每个字母遍历，我的代码复制上去的时候有点问题，很多index都看不到，但我test了下是可以的。

cbwcs 发表于 2015-9-23 01:54
楼主，我的想法跟你基本一致，但不需要用到map,开个数组就好，因为都是lowcase的。
然后只需要记录S的ch ...

嗯，思路确实差不多，不过
  for(int i=0; i<s.size(); i++)
        {
                hash[s-'a'].push_back(i);
        }
如果记录所有的idex，而不是当 S[i] != T[i] 的index，在你交换的时候，可能交换之前他们本身就是相等的。
所以为觉得是不是只记录不相等的更合理些？