【leetcode】Anagrams (middle)

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

Note: All inputs will be in lower-case.

anagrams 的意思是两个词用相同的字母组成  比如 “dog" "god"

思路:

把单词排序 如 dog 按字母排序变为 dgo

用unordered_map<string, int> 记录排序后序列第一次出现时,字符串在输入string向量中的位置

用vector<bool> 记录每个输入字符串是否为anagram, 如果在map中发现已经存在了,就记录当前和初始的字符串都是anagram

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        vector<string> ans;
        vector<bool> isanagrams(strs.size(), false);
        unordered_map<string, int> hash;
        if(strs.size() == 0)
            return ans;

        for(int i = 0; i < strs.size(); i++)
        {
            string cur = strs[i];
            sort(cur.begin(), cur.end());
            if(hash.find(cur) == hash.end()) //没出现过
            {
                hash[cur] = i; //记录第一次出现是strs中的哪一个
            }
            else //出现过
            {
                isanagrams[hash[cur]] = true;
                isanagrams[i] = true;
            }
        }

        for(int j = 0; j < strs.size(); j++)
        {
            if(isanagrams[j] == true)
            {
                ans.push_back(strs[j]);
            }
        }

        return ans;
    }
};
时间: 03-10

【leetcode】Anagrams (middle)的相关文章

【LeetCode】Anagrams 解题报告

[题目] Given an array of strings, return all groups of strings that are anagrams. Note: All inputs will be in lower-case. [解析] 题意:给定一个字符串数组,返回所有是"换位词"的字符串. 所谓"换位词/变位词"就是包含相同字母,但字母顺序可能不同的字符串.比如"abc", "bca", "cab&q

【leetcode】Anagrams

Anagrams Given an array of strings, return all groups of strings that are anagrams. Note: All inputs will be in lower-case. Anagrams:即字母个数和字母都相同,但是字母顺序不相同的词 e.g. "tea","and","ate","eat","dan".   return &qu

【leetcode】Combinations (middle)

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example,If n = 4 and k = 2, a solution is: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 思路:有点像0-1背包问题, 对于从1-n的每一个数字都可以选择放入答案 和不放入答案. 当长度达到k时就是一个符合条件的解. 递归的

【leetcode】Permutations (middle)

Given a collection of numbers, return all possible permutations. For example,[1,2,3] have the following permutations:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. 求没有重复数字的全排列 思路:用的标准回溯法,一次AC class Solution { public: vector<vector<int>

【leetcode】Pascal&#39;s Triangle I &amp; II (middle)

Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5,Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 思路:杨辉三角,直接按规律生成即可 vector<vector<int> > generate(int numRows) { vector<vector<int>>

【LeetCode】 Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6. More practice: If you have figu

【Leetcode】Unique Paths II

Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middl

【Leetcode】Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous ro

【LeetCode】Unique Paths II 解题报告

[题目] Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the