Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Anagrams

Leetcode algorithms 第 49 题:Anagrams。

题目

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

Note: All inputs will be in lower-case.

解答

找到一组字符串中属于anagrams的所有字符串,anagrams指的是由相同的单词以不同的顺序组成的单词,比如abc和bac属于anagrams。由于仅仅是顺序不同,那么把字符串排序后,所有的anagrams都会变成同一个单词,于是使用map进行保存。

具体代码如下:

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        map<string, int> mp;
        vector<string> ans;
        for (int i = 0; i < strs.size(); i++)
        {
            string tem = strs[i];
            sort(tem.begin(), tem.end()); //排序,使anagrams变得一样
            if (mp.find(tem) == mp.end())
                mp[tem] = i;
            else
            {
                if (mp[tem] >= 0) //已有anagrams,保存第一个
                    ans.push_back(strs[mp[tem]]), mp[tem] = -1; 
                ans.push_back(strs[i]);
            }
        }
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论