轉自：http://zhedahht.blog.163.com/blog/static/25411174200801931426484/
題目：輸入兩個字元串，從第一字元串中删除第二個字元串中所有的字元。例如，輸入”they are students.”和”aeiou”，則删除之後的第一個字元串變成”thy r stdnts.”。
分析：這是一道微軟面試題。在微軟的常見面試題中，與字元串相關的題目占了很大的一部分，因為寫程式操作字元串能很好的反映我們的程式設計基本功。
要程式設計完成這道題要求的功能可能并不難。畢竟，這道題的基本思路就是在第一個字元串中拿到一個字元，在第二個字元串中查找一下，看它是不是在第二個字元串中。如果在的話，就從第一個字元串中删除。但如何能夠把效率優化到讓人滿意的程度，卻也不是一件容易的事情。也就是說，如何在第一個字元串中删除一個字元，以及如何在第二字元串中查找一個字元，都是需要一些小技巧的。
首先我們考慮如何在字元串中删除一個字元。由于字元串的記憶體配置設定方式是連續配置設定的。我們從字元串當中删除一個字元，需要把後面所有的字元往前移動一個位元組的位置。但如果每次删除都需要移動字元串後面的字元的話，對于一個長度為n的字元串而言，删除一個字元的時間複雜度為o(n)。而對于本題而言，有可能要删除的字元的個數是n，是以該方法就删除而言的時間複雜度為o(n2)。
事實上，我們并不需要在每次删除一個字元的時候都去移動後面所有的字元。我們可以設想，當一個字元需要被删除的時候，我們把它所占的位置讓它後面的字元來填補，也就相當于這個字元被删除了。在具體實作中，我們可以定義兩個指針(pfast和pslow)，初始的時候都指向第一字元的起始位置。當pfast指向的字元是需要删除的字元，則pfast直接跳過，指向下一個字元。如果pfast指向的字元是不需要删除的字元，那麼把pfast指向的字元指派給pslow指向的字元，并且pfast和pstart同時向後移動指向下一個字元。這樣，前面被pfast跳過的字元相當于被删除了。用這種方法，整個删除在o(n)時間内就可以完成。
接下來我們考慮如何在一個字元串中查找一個字元。當然，最簡單的辦法就是從頭到尾掃描整個字元串。顯然，這種方法需要一個循環，對于一個長度為n的字元串，時間複雜度是o(n)。
由于字元的總數是有限的。對于八位的char型字元而言，總共隻有28=256個字元。我們可以建立一個大小為256的數組，把所有元素都初始化為0。然後對于字元串中每一個字元，把它的ascii碼映射成索引，把數組中該索引對應的元素設為１。這個時候，要查找一個字元就變得很快了：根據這個字元的ascii碼，在數組中對應的下标找到該元素，如果為0，表示字元串中沒有該字元，否則字元串中包含該字元。此時，查找一個字元的時間複雜度是o(1)。其實，這個數組就是一個hash表。這種思路的詳細說明。
基于上述分析，我們可以寫出如下代碼：
總結：空間換取時間
在字元串中删除特定的字元