UVa 195 - Anagram

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址

Solution

解法沒有什麼特別，只是單純做回溯法，一一列出字串，並注意同一位置不要取到相同的字母。

倒是在使用 std::sort 排序時遇到了個問題，原先裡面的 compare 寫法是這樣：

char aa = tolower(a), bb = tolower(b);
if (aa != bb)                           //字母不同
    return aa < bb;                     //比順序
else                                    //字母一樣，但可能一個大寫
    return (a >= 'A' && a <= 'Z');      //大寫在前

雖然先通過了，但在字串是同一大寫字母且超過 16 個時，會出錯。例如：AAAAAAAAAAAAAAAAA (Ax17)。
查了一下才察覺 return (a >= 'A' && a <= 'Z') 會造成未定義的行為，因為它並不是個 strict weak ordering。
所以之後改成了 return a < b 就沒問題了。

而超過 16 個才會錯似乎是因為當元素超過 16 個，std::sort 就會使用基於快速排序的方法，
此時 strict weak ordering 就會對結果產生影響了。

相關資料：
https://stackoverflow.com/questions/18291620/why-will-stdsort-crash-if-the-comparison-function-is-not-as-operator?lq=1
http://blog.csdn.net/jiange_zh/article/details/78240806
http://fusharblog.com/3-ways-to-define-comparison-functions-in-cpp/

Code

UVa 195

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#define N 105

bool used[N];
char ans[N];
void backtrack(char *str, int now, const int &len)
{
    if (now == len)
    {
        ans[len] = '\0';
        puts(ans);
        return;
    }

    char last = '\0'; //防止選一樣的
    for (int i = 0; i < len; i++)
    {
        if (!used[i] && str[i] != last)
        {
            used[i] = true;
            ans[now] = str[i];
            backtrack(str, now + 1, len);
            used[i] = false;
            last = str[i];
        }
    }
}
int main()
{
    int n;
    char str[N];
    scanf("%d ", &n);
    while (n--)
    {
        fgets(str, N, stdin);
        int len = strlen(str);
        if (str[len - 1] == '\n')
            str[--len] = '\0';

        std::sort(str, str + len,
                  [](const char &a, const char &b) -> bool {
                      char aa = tolower(a), bb = tolower(b);
                      if (aa != bb)       //字母不同
                          return aa < bb; //比順序
                      else                //字母一樣，但可能一個大寫
                          return a < b;   //大寫在前
                  });

        backtrack(str, 0, len);
    }

    return 0;
}