Skip to main content

Day 5: Group Anagrams - leetcode - Python3

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

 

Constraints:

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

SOLUTION:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res: defaultdict[list]=defaultdict(list)

        for word in strs:
            count=[0] * 26 #a-z

            for char in word:

                count[ord(char) - ord("a")] +=1 #KEY

            res[tuple(count)].append(word)
            #converts the list to a tuple, and uses it as
            #a key to store the words in the res dictionary
        return res.values()
  • Time complexity:

O(n+m)O(n + m)

  • Space complexity:

O(n+m)O(n + m)O(n + u), where n is the number of words in strs and u is the number of unique anagram patterns.

Let's break down how the code works:

  1. The code defines a class named Solution that contains a method groupAnagrams. The method takes a parameter strs, which is a list of strings, and returns a list of lists of strings.

  2. It initializes a defaultdict named res using the collections module. This dictionary-like object will automatically create an empty list as the default value for any key that does not exist.

  3. It iterates over each word in the input list strs.

  4. For each word, it creates a count list of 26 integers initialized to 0. This list will be used to count the frequency of each character in the word.

  5. It iterates over each char in the current word.

  6. For each char, it calculates the index by subtracting the ASCII value of "a" from the ASCII value of the current character using the ord() function. This index represents the corresponding position in the count list.

  7. It increments the count at the calculated index by 1.

  8. It converts the count list to a tuple and uses it as a key to access the res dictionary.

  9. It appends the current word to the list associated with the calculated key in the res dictionary.

  10. After iterating over all the words, it returns the values of the res dictionary as the final result. The values are a list of lists, where each inner list contains anagrams grouped together.

In summary, It counts the frequency of each character in each word using a count list, converts the list to a tuple, and uses it as a key to store the words in the res dictionary. Finally, it returns the grouped anagrams as a list of lists.

Comments

Popular posts from this blog

Bug Boundy Methodology, Tools & Resources

Start by defining a clear objective, such as exploiting a remote code execution (RCE) vulnerability or bypassing authentication on your target. Then, consider how you can achieve this goal using various attack vectors like XSS, SSRF, or others - these are simply tools to help you reach your objective. Use the target as how a normal user would, while browsing keep these questions in mind: 1)How does the app pass data? 2)How/where does the app talk about users? 3)Does the app have multi-tenancy or user levels? 4)Does the app have a unique threat model? 5)Has there been past security research & vulnerabilities? 6)How does the app handle XSS, CSRF, and code injection?

Install & set up mitmweb or mitmproxy in Linux

Step 1: Go to the mitmproxy page and download the binaries. Step 2: Install the downloaded tar file with the command " tar -xzf <filename>.tar.gz " Step 3: In the FoxyProxy add the proxy 127.0.0.1:8080  and turn it on. Step 4 : In the terminal run command " ./mitmweb " Step 5: Go to the page  http://mitm.it/   and download the mitmproxy's Certificate. Step 6: If you downloaded the certificate for Firefox, then go to " settings -> Privacy & Security -> Click View Certificates -> Click  Import ", then import the certificate.  Step 7: Now you are ready to capture the web traffic. Step 8 : In terminal run " ./mitmweb"

Making CHIP-8 emulator in C

  Chip8 doc link | Components | Opcode Table GitHub - AdithyakrishnaV/Chip8_Emulator--Interpreter Contribute to AdithyakrishnaV/Chip8_Emulator--Interpreter development by creating an account on GitHub. github.com CHIP-8 programs are binary files, and your emulator must read them and operate on the bytes. You will also need a way to draw graphics to the screen and read keypresses. Many graphical libraries can do this for you or use something like SDL directly. CHIP-8 components Display 64 pixels wide and 32 pixels tall. Each pixel is a boolean value, or a bit; can be on or off (“off” pixel was just black, and “on” was white). We’ll use SDL for rendering: SDL initialization Not initialize:- returns -1  Error message is stored in SDL_GetError Initializing SDL if (SDL_Init(SDL_INIT_VIDEO)!= 0 ){ printf ( "SDL not initialized,%s\n" , SDL_GetError); exit (- 1 ); } Initialize display SDL_Window * window = SDL_CreateWindow ( "chip8" , SDL_WINDOWPOS_CENTERED , SDL_...