Chapter 1 | Arrays and Strings--判斷變位詞和字元串空格替換為‘ ’

1.4    Write a method to decide if two strings are anagrams or not.

譯文：寫一個函數判斷是否兩個字元串為變位詞。變位詞就是兩個字元串中的字元相同，隻是位置不同

這裡似乎又涉及到了字元的重複問題，通過前面幾個小節的說明，可以借助一個數組來表征字元的出現，不過這裡是兩個字元串，我們可以采用同一個數組，對一個字元串中的字元出現來設定數組中的對應位置加1，對另一個字元串則相應位置減1，有點類似于C++中的智能指針，最後來判斷這個數組是否為空，為空，表示為變位詞，否則不是。代碼

bool isAnagrams(string str, string dst)
{
	if ((str.length() != dst.length()) || (0 == str.length()))
		return false;

	int len = str.length();
	int a[256];
	memset(a, 0, sizeof(a));
	for (int i = 0; i < len; ++i)
	{
		++a[(int)str[i]];
		--a[(int)dst[i]];
	}

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

另外也可以對字元串中的字元進行排序，然後比較兩個字元串，如果相同則是變位詞，否則不是。

可以借助标準庫中的排序算法直接對字元串進行排序。這裡還是貼一下快排的代碼

int Partition(char s[], int left, int right)
{
    int pivot = s[left];

    while (left < right)
    {
        while (left < right && s[right] > pivot) //兩種情況跳出循環
            --right;
        s[left] = s[right];                      //left == right時亦滿足

        while (left < right && s[left] <= pivot)
            ++left;
        s[right] = s[left];                      //left不斷變化
    }
    s[left] = pivot;
    return left;
}

void QuickSort(char s[], int left, int right)
{
    if (left < right)
    {
        int i = Partition(s, left, right);
        QuickSort(s, left, i - 1);
        QuickSort(s, i + 1, right);
    }
}

bool isAnagrams(string str, string dst)
{
    if ((str.length() != dst.length()) || (0 == str.length()))
        return false;

    int len = str.length();

    QuickSort(&str[0], 0, len - 1);
    QuickSort(&dst[0], 0, len - 1);

    if (str == dst)
        return true;
    else
        return false;
}
           

相比第一種方法這看起來複雜點，這裡隻是提供一下思路，不過借助庫函數中的排序函數sort會很簡潔。

1.5    Write a method to replace all spaces in a string with ‘%20’.

譯文：寫一個函數将字元串中的所有空格用‘%20’替換。這道題其實就是 URL中的空格替換為 %20。

一個空格占一個字元位，‘%20’占用3個字元位，是以替換後需要更大的空間，這不得不另外開辟一個更大的數組空間來存放。首先得周遊一遍字元串，計算出字元串中空格的個數，然後針對每個空格需要額外添加2個字元空間開辟一個新的數組，代碼

char* replace_space(char *str)
{
	if (NULL == str)
		return NULL;

	int len = strlen(str);
	if (len < 1)
		return NULL;

	int cnt = 0;
	for (int i = 0; i < len; ++i)
	{
		if (' ' == str[i])
			cnt++;
	}

	char *dst = new char[len + 2*cnt + 1];
	int p = len + 2 * cnt;
	dst[p--] = '\0';

	for (int i = len - 1; i >= 0; --i)  //從後往前
	{
		if (' ' == str[i])
		{
			dst[p] = '0';
			dst[p - 1] = '2';
			dst[p - 2] = '%';
			p -= 3;
		}
		else
		{
			dst[p--] = str[i];
		}
	}
	return dst;
}
           

值得注意的是，将字元串放到另外一個數組中時，需要從後面往前面周遊。