Cracking the coding interview-String

關於字元串

問題描述：一般這類程式設計的題目較簡單，通過設計字元串的反轉，尋找子串，以及字元串的拼接、刪除操作等問題。

問題

• 實現一個演算法來判斷一個字元串中的字元是否唯一(即沒有重覆)？
• 設計演算法並寫出代碼移除字元串中重覆的字元（不能使用額外的緩存空間）？
• 寫一個函數判斷兩個字元串是否是變位詞?

思路

這三個題目，幾乎都要對字元串進行遍歷，在遍歷中尋求一些邏輯上的計算。

對於第一題，直接遍歷判斷是否後一個字元和前一個字元是否相同，這樣時間複雜度就會很大，相比於把字元的Ascll碼直接作為數組的下標，是個不錯的選擇，這樣大大提高了時間效率，不過需要藉助一些額外的記憶體空間。

對於第二題，由於不可以使用額外的緩存空間，則就考慮直接把重覆的字元設置標誌，然後把沒有設置標誌的字元輸出來，就能達到最後的效果。

對於第三題，需要遍歷字元串，統計重覆的字元，也可以把他作為一個數組的下標，這樣兩個額外的數組裡的值相同，即就是“變位詞”，不同就不是；或者將每個字元串，排序，如果相同，則是“變位詞”，如果不同，則不是“變位詞”。

需要註意的是：在運用到"char"數組的時候不要忘記了，最後位置上的結束符"\n"。還有就是聲明的一個數組，最好事先初始化。

主要代碼

1、判斷字元串中字元是否唯一

//O(n*n)
bool isUnique(string str)   
{
    int i, j;
    int length = str.length();
    for (i = 0; i < length; i++)
    {
        for (j = i + 1; j < length; j++) 
        {
            if (str[i] == str[j])
            {
                return false;
                break;
            }
        }
    }
    if (j == length) return true;
}

//O(n)
bool isUnique1(string str)
{
    int v;
    bool s[256];
    //初始化比較大的數組
    memset(s, 0, sizeof(s));
    int length = str.length();
    for (int i = 0; i < length; i++)
    {
        v = (int)(str[i]);
        if (s[v]) 
        {
            return false;
        }
        s[v] = true;
    }
    return true;
}

2、移除重覆字元

void removeDuplicate(char s[])
{
    int length = strlen(s);
    int i, j;
    for (i = 0; i < length; i++)
    {
        for (j = i + 1; j < length; j++)
        {
            if (s[i] == s[j])
            {
                s[j] = ' '; //空格的ascll為32
            }
        }

        if (s[i] != ' ')
        {
            cout << s[i];
        }
    }

    cout << endl;
}

3、字元串是否是變位詞

bool isAnagrams1(string a, string b)
{
    if (a == " " || b == " ")
    {
        return false;
    }
    if (a.length() != b.length())
    {
        return false;
    }
    if (a == b)
    {
        return false;
    }
    //sort
    sort(&a[0], &a[0] + a.length());
    sort(&b[0], &b[0] + b.length());

    if (a == b)
    {
        return true;
    }
    else
        return false;
}

bool isAnagrams2(string a, string b)
{
    int c[256];
    memset(c, 0, sizeof(c));

    if (a == "" || b == "")
    {
        return false;
    }

    if (a.length() != b.length())
    {
        return false;
    }

    if (a == b)
    {
        return false;
    }

    for (int i = 0; i < a.length(); i++)
    {
        c[(int)a[i]] += 1;
        c[(int)b[i]] -= 1;
    }

    for (int i = 0; i < 256; i++)
    {
        if (c[i] != 0)
        {
            return false;
            break;
        }
    }

    return true;
}

Note：本文一些思路及題目翻譯摘自於http://www.hawstein.com/