Showing posts from July, 2021

Bijective Mapping

This was an interesting backtracking problem from Leetcode:  Word Pattern II - LeetCode 291. Word Pattern II Medium 571 41 Add to List Share Given a  pattern  and a string  s , return  true  if  s   matches  the  pattern . A string  s   matches  a  pattern  if there is some  bijective mapping  of single characters to strings such that if each character in  pattern  is replaced by the string it maps to, then the resulting string is  s . A  bijective mapping  means that no two characters map to the same string, and no character maps to two different strings.   Example 1: Input: pattern = "abab", s = "redblueredblue" Output: true Explanation: One possible mapping is as follows: 'a' -> "red" 'b' -> "blue" Example 2: Input: pattern = "aaaa", s = "asdasdasdasd" Output: true Explanation: One possible mapping is as follows: 'a' -> "asd" Example 3: Input: pattern = "abab", s =

Brute-force based on hints II

Yeah for this problem I wanted to know if it was possible to go with a brute-force approach. So I looked at the hints, and sure enough, it says that brute-force is OK, so that's what I did. Brute-forcing it with backtracking. Code is below, cheers, ACC. Maximum Compatibility Score Sum - LeetCode 1947. Maximum Compatibility Score Sum Medium 132 4 Add to List Share There is a survey that consists of  n  questions where each question's answer is either  0  (no) or  1  (yes). The survey was given to  m  students numbered from  0  to  m - 1  and  m  mentors numbered from  0  to  m - 1 . The answers of the students are represented by a 2D integer array  students  where  students[i]  is an integer array that contains the answers of the  i th  student ( 0-indexed ). The answers of the mentors are represented by a 2D integer array  mentors  where  mentors[j]  is an integer array that contains the answers of the  j th  mentor ( 0-indexed ). Each student will be assigned to  one  mentor,

Project Euler: Concatenation and Coincidences

Has been a while (one year) since I've tackled a Project Euler  (PE) problem. This is my 205th Euler problem solved (after problem 100th, it gets really intense). It is rare that the gods of PE release any easy problem these days, but since this one had a difficult rating of 5% (which is the easiest for a PE), I decided to take a look today. One note thou: I can't post neither the solution (which is a number) nor the code to produce the solution since the PE gods will track you down and suspend your account, so I'll just talk in high-level terms about the problem without disclosing much of the solution. Here is the problem:  Problem 751 - Project Euler I can at least talk about the implementation of the function to generate An. It is actually fairly straightforward: 1/ I didn't do it recursively 2/ It is a combination of using the Floor function and simple concatenation rules You can see the code down below for the concatenation function. Once I had that function I star

Grid - Breadth First Search (BFS) - III

LeetCode just loves to bring BFS problems. This one is very similar to the previous ones related to grids (in the case here it is a Maze, but the idea is the same). Nothing really different in this problem that is worth explaining further, so just enjoy the code down below - cheers, ACC. Nearest Exit from Entrance in Maze - LeetCode 1926. Nearest Exit from Entrance in Maze Medium 115 10 Add to List Share You are given an  m x n  matrix  maze  ( 0-indexed ) with empty cells (represented as  '.' ) and walls (represented as  '+' ). You are also given the  entrance  of the maze, where  entrance = [entrance row , entrance col ]  denotes the row and column of the cell you are initially standing at. In one step, you can move one cell  up ,  down ,  left , or  right . You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the  nearest exit  from the  entrance . An  exit  is defined as an  empty cell  that is at the  border  of the  m

Reshaping a matrix

874th solved. Goal is to transform a matrix AxB into another one CxD. First if the dimensions don't match (A*B != C*D) then you just return the original matrix. Otherwise you do a pass on CxD and keep a row and col variables tracking the first matrix, changing them accordingly. Code is down below, cheers, ACC. Oh, and here is me in the ACM collegiate contest, some time in a different century... Reshape the Matrix - LeetCode 566. Reshape the Matrix Easy 1178 130 Add to List Share In MATLAB, there is a handy function called  reshape  which can reshape an  m x n  matrix into a new one with a different size  r x c  keeping its original data. You are given an  m x n  matrix  mat  and two integers  r  and  c  representing the row number and column number of the wanted reshaped matrix. The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were. If the  reshape  operation with given parameters is possible and legal, outpu

Modular math...

872nd problem solved: just do the modular math for this problem. Basically you'll need to do this: 5^(even positions) * 4^(odd positions) All that mod 10^9 + 7. Code is below, hugs to everyone!!! ACC Count Good Numbers - LeetCode 1922. Count Good Numbers Medium 92 100 Add to List Share A digit string is  good  if the digits  (0-indexed)  at  even  indices are  even  and the digits at  odd  indices are  prime  ( 2 ,  3 ,  5 , or  7 ). For example,  "2582"  is good because the digits ( 2  and  8 ) at even positions are even and the digits ( 5  and  2 ) at odd positions are prime. However,  "3245"  is  not  good because  3  is at an even index but is not even. Given an integer  n , return  the  total  number of good digit strings of length  n . Since the answer may be large,  return it modulo  10 9  + 7 . A  digit string  is a string consisting of digits  0  through  9  that may contain leading zeros.   Example 1: Input: n = 1 Output: 5 Explanation: The good num