首页 > 基础算法 > 字符串处理 > LeetCode-Anagrams[字符串]
2014
11-19

LeetCode-Anagrams[字符串]

Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

标签: Hash Table String
分析

Anagram(回文构词法)是指打乱字母顺序从而得到新的单词,比如 {"dormitory"} 打乱字母顺序会变成 {"dirty room"} ,{"tea"} 会变成{"eat"}。

回文构词法有一个特点:单词里的字母的种类和数目没有改变,只是改变了字母的排列顺序。因此,将几个单词按照字母顺序排序后,若它们相等,则它们属于同一组 anagrams 。

代码1

// LeetCode, Anagrams
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        unordered_map<string, vector<string> > group;
        for (const auto &s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            group[key].push_back(s);
        }

        vector<string> result;
        for (auto it = group.cbegin(); it != group.cend(); it++) {
            if (it->second.size() > 1)
                result.insert(result.end(), it->second.begin(), it->second.end());
        }
        return result;
    }
};

  1. 这解法太慢了,还是把ARRAY 当HASH来得快,而且看完字符时不要复查ARRAY,另设一个COUNT看0就行了。

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }