Skip to content

Word Pattern

Jump to bottom
Linda Zhou edited this page Dec 4, 2022 · 6 revisions

Problem Highlights

  • 🔗 Leetcode Link: <>
  • 💡 Problem Difficulty: Medium
  • ⏰ Time to complete: __ mins
  • 🛠️ Topics: Hash Table
  • 🗒️ Similar Questions:

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

Run through a set of example cases:

HAPPY CASE



EDGE CASE

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

  • Stack: What could we push onto a stack to make this problem easier? Stacks don’t allow us to keep track of data based on keys.
  • Queue: Queues fall into the same category as Stacks, do we need to maintain any sense of ordering to solve this problem?
  • HashMap: HashMaps allow us to store data for quick access. What could we store in a HashMap to make this problem easier?
  • Heap: Do we need some sort of ordering to our data that a Heap could provide?

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:



⚠️ Common Mistakes


    

  • Some people may try to approach this problem initially with some brute force O(N^2) strategy. However, this approach doesn’t work. Try to urge students to avoid usual brute force tactics. Instead, urge them to use known data structures to solve this problem.
    • 



4: I-mplement




Implement the code to solve the algorithm.








5: R-eview




Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.




    

  • Trace through your code with an input to check for the expected output
    • 

  • Catch possible edge cases and off-by-one errors
    • 



6: E-valuate




Evaluate the performance of your algorithm and state any strong/weak or future potential work.




    

  • 
Time Complexity:
    • 

  • 
Space Complexity: O(N), required to maintain hashmap.
    • 



              


          



  
          

            


            
Clone this wiki locally