【劍指offer】删除在另一個字元串中出現的字元

轉載請注明出處：

    劍指offer上的字元串相關題目。 

    題目：輸入兩個字元串，從第一字元串中删除第二個字元串中所有的字元。例如，輸入”They are students.”和”aeiou”，則删除之後的第一個字元串變成”Thy r stdnts.”。

    這裡主要要分析兩個方面：

    1、如何判斷那些字元是需要删除的字元。同很多字元串問題一樣，可以開辟一個哈希數組，全部初始化為false，将第二個字元串中字元對應的映射位置置為ture，表示這些位置對應的字元在第一個字元串中需要删除。

    2、關于删除字元的操作，每次删除一個，而後把後面的元素均左移一位，由于要删除的字元可能有多個，這種方法的時間複雜度為O（n*n）。我們這裡有O（n）的删除方法，我們可以設想，當一個字元需要被删除的時候，我們把它所占的位置讓它後面的字元來填補，也就相當于這個字元被删除了。在具體實作中，我們可以定義兩個指針(pFast和pSlow)，初始的時候都指向第一字元的起始位置。當pFast指向的字元是需要删除的字元，則pFast直接跳過，指向下一個字元。如果pFast指向的字元是不需要删除的字元，那麼把pFast指向的字元指派給pSlow指向的字元，并且pFast和pStart同時向後移動指向下一個字元。這樣，前面被pFast跳過的字元相當于被删除了。用這種方法，整個删除在O(n)時間内就可以完成。

    前面也有篇删除重複字元的博文用到了該删除方法，見這裡：。

    另外，有一點需要注意，char的範圍在-128-127，unsigned char的範圍才是在0-255，是以ASCII值在128-255之間的字元，如果儲存為了char型，其轉化為int值的範圍是在-128--1之間，這點在下面的代碼中有展現。

    根據以上思路寫出的代碼如下：

    測試結果：