實現字元串替換函數char *strReplace(const char *original,const char *substr,const char *replace)？

某IT公司面試題：把源字元串original中的子串substr替換成replace子串並返回。求大神能給出一個高效解法。我目前存在問題：短時間內寫不出高效的演算法，寫個很low的演算法又過不了面試。也不習慣讓面試官等十分鐘看我寫代碼。面試官會不會在意麵試者花很長時間紙上寫代碼。遇到這種情況怎麼解決？短時間寫個low代碼還是長時間寫個相對高效的代碼？

---

謝邀，我想好好的回答一下這個問題。

對於這個問題，首先情景是在面試場合，那麼若我是面試者的話，我會選擇先短時間實現一個可以工作的代碼，然後再和面試官一起交流，探尋更高效的實現（前提他是一個好的面試官），而如果我是面試官的話，如果出這道題，我觀察的不僅是他的實現，也觀察他的編碼習慣，Corner Case的考慮，他的思維過程等，如這道題目，他一上來就啪啪啪的吭哧吭哧的寫了，一上來就沒有判定指針是否為空，就直接用了，那麼這樣的話，會減分不少。所以，正是如此，作為面試者，也需要揣摩出面試官的心理，針針入血，刺激到他的High點，產生相見恨晚的感覺那就基本上成功了。

而面試中，最好不要沉默，而要展現自己，如與面試官確定需求條件，這樣也可以為自己贏得更多的一些時間思考，也表明自己是一個編碼很謹慎的人，具有著職業精神，而非學生時期的那麼衝動了。

而在實現這道題目的時候，你有幾種方向，一種是測試驅動，即你先寫單元測試用例，然後再實現，對面試官表明我的開發是有測試做積澱的，是有支撐的，而非盲目的想當然是怎麼樣的。第二種是直接先實現，再測試。即理清楚了需求，就直接實現，然後再來寫單元測試用例來驗證自己的實現是否正確。當然，這到底哪種好呢？我相信會有不同的看法，當然我更傾向於第一種。

隨後在開始實現的時候，你可以邊實現邊展現你的思路是怎麼樣，並對一些該強調的地方進行強調，如這道題目，第一步判定original是否為空指針，寫完後你就可以給面試官說了，然後讓面試官意識到你是知道這個的，同時你可以給面試官再次確認，如果遇到這樣的情況，我們應該是返回為NULL呢，還是說有其他的處理方式，或者說我們採用assert？當然這都是可以商量的。也許你會說很愚蠢，怎麼婆婆媽媽的，這都是在為自己贏取時間，並且表明自己是很謹慎的，有職業素養的程序員。然後，與此同時，substr，replace為NULL的時候，我們應該返回NULL，還是strdup等等，抑或怎麼樣？這些都是需要確認的。於是，實現可能是這樣的：

char* strReplace(const char *original, const char *substr, const char *replace)
{
char *tok = NULL;
char *newstr = NULL;
char *oldstr = NULL;
char *head = NULL;

if (original == NULL || substr == NULL || replace == NULL)
{
return NULL;
}

newstr = strdup(original);
head = newstr;
while ((tok = strstr(head, substr)))
{
oldstr = newstr;
newstr = (char*) malloc(strlen(oldstr) - strlen(substr) + strlen(replace) + 1);
/*failed to alloc mem, free old string and return NULL */
if (newstr == NULL)
{
free(oldstr);
return NULL;
}
memcpy(newstr, oldstr, tok - oldstr);
memcpy(newstr + (tok - oldstr), replace, strlen(replace));
memcpy(newstr + (tok - oldstr) + strlen(replace), tok + strlen(substr), strlen(oldstr) - strlen(substr) - (tok - oldstr));
memset(newstr + strlen(oldstr) - strlen(substr) + strlen(replace), 0, 1);
head = newstr + (tok - oldstr) + strlen(replace);
free(oldstr);
}
return newstr;
}


然後如果我是面試官，我這時候可能就會有幾個問題

1. 既然用了memcpy，那麼他是否也可以自己實現memcpy呢？而作為面試官，實際考察點，可能不在於此，而在於他是否知道地址重疊，以及怎麼處理

2. 能否有更高效的版本實現呢？

那麼作為面試者，當被問住實現memcpy的時候，同樣要清楚，其實既然這麼考，自然有更深層次的考察，如果此時能知道地址重疊的情況，並知道如何處理，那就非常的棒了，因為刺激到了面試官的High點，抓住了他的意圖。

而作為面試官，問有沒有更高效的版本實現，是希望更深層次的知道他到底有多強，也是想繼續拓展一下話題。那麼面試者這時候也許就會想到，我們對字元串的處理，這時候可能這個字元串有很多需要替換的，其實這裡面會有一個隱藏的計數count，那麼我們也許可以考慮實現一個帶Cache Position的版本。OK，這時候，面試者可能就吭哧吭哧的講解Cache，然後實現Cache版本，這個時候，面試官也抓住了一個話題聊下去，如是否知道L1 Cache，L2 Cache，L3 Cache，區別？是否知道MemCached這東西？如果用過MemCached，就有的聊了，如果沒有用過，沒有關係，那麼可以從L1 Cache這個話題開始。然後，作為面試官可以繼續拓展到CPU的相關知識，如Program Counter，指令周期等等，而作為面試者，這個時候則需要知道的是，考這些內容是在測自己的專業深度，不要心裡埋怨平時開發根本用不上這東西，怎麼考這麼煞筆的問題，而應該將自己平時積累的專業深度知識都拿出來。聊完計算機組織結構知識，很容易就可以聊到操作系統知識，聊到編譯器的知識，甚至於說對於面試者重新寫Cache版本的時候，可以聊到重構，可以聊到設計模式，這樣可以測出面試者的專業知識廣度，這樣的話，面試者的能力也能最大化的被測出來。

於是，作為面試者，可以發現自己所寫的每一行代碼，每一處細節都可以作為面試官的話題延伸點，那麼面試者寫下每一行代碼的時候都要有把握解釋清楚到底發生了什麼，而且如果面試者足夠的聰明，在寫下代碼的時候，甚至可以引導面試官往哪方面來問，如在實現這個函數的時候，作為面試者，我可能就會想面試官會有幾個地方可能詢問： 1. strstr的用法和實現 2. memcpy的用法與實現，乃至於memmove的比較. 那麼當出現上述問了高效版本的時候，其實對自己是更有利的，因為提高性能的辦法其實有各種方式，如果強在計算機組織等，則可以往寄存器，Cache等低層次的說，如果強在演算法方面，可以往更快的演算法方面走。這個時候，在重構的時候，面試者自然也要留個心眼，進行漂亮的重構，乃至考慮到可維護性，可擴展性等方面，這樣也是對自己能力的一個很好的展現。

於是，如果是一個好的面試官，很容易就能測出來面試者的水平。如果是一個好的面試者，也很容易能夠展現出自己的能力，乃至引領面試官進入到自己的節奏。而這兩者，我個人覺得其實更難做的是一個好的面試官，因為面試官需要實時評估，而面試者需要的僅是很好的展示自己。

---

strReplace("abcabc", "abc", " abcabc") 應該返回什麼？

---

這是**二面的面試題吧，我正好也做了這題，不過答的不好。時間這麼短面試官主要還是看思路和編碼習慣吧，盡量保證不crash。面試官不會讓你長時間寫的，我當時還沒寫完就被他打斷了，聊聊思路就過了

---

自己先寫個簡單的，權當拋磚引玉，也許自己真的太菜，不適合干程序員，拼不過大神

char *strReplace(const char *original, const char *substr, const char *replace) {
if(original == NULL )
return NULL;
char *res = (char*) malloc(strlen(original) + 1);
strcpy(res, original);
if (substr == NULL || strstr(original, substr) == NULL)
return res;
string ans;
int len = strlen(original), sublen = strlen(substr), replacelen = strlen(replace);
string s_original = original, s_substr = substr, s_replace = replace;
for (int i = 0; i &< len;) { if (s_original.substr(i, sublen) == s_substr) { ans += s_replace; i += sublen; } else { ans += s_original[i++]; } } char *res1 = (char*) malloc(ans.length() + 1); for (int i = 0; i &< ans.length(); i++) res1[i] = ans[i]; res1[ans.length()] = ""; return res1; }

---

推薦閱讀：