CODEWITHSUNDEEP
javascriptalgorithm
Ömer Hattapoğlu
Ömer Hattapoğlu

Reputation: 68

Function that gives minimum strokes required for a given array of strings

It is given an array of strings. Strings have same length. Assuming input array is (["ababc", "abbba", "aaabb", "bcccb", "acbbb", "aaabb"]).

a b a b c
a b b b a
a a a b b
b c c c b
a c b b b
a a a b b

The problem is about finding minimum connected groups of letters, it is possible to sketch vertically and horizontally for the same letter but not diagonally. For this example, there are 4 groups for letter 'a' (two single, two multiple), 2 groups for letter 'b' (one single, one multiple) and 2 groups for letter 'c' (one single, one multiple). So, the output should be "8". I couldn't find a solution using JavaScript.

I've tried to consider it as seperate rows and columns. Moreover, creating arrays for each character and analyze it seperately. But never of them works correctly.

function strokesRequired(picture){
        let total = picture.join('');
        let strLength = picture[0].length;
        let counter = 0;
        for(let i = 0; i < total.length; i++){
          if(total[i] !== total[i+1] || total[i] !== total[i+strLength] || total[i] !== total[i-1] || total[i] !== total[i-strLength]){
            continue;
         }
         else {        
            counter++;
          }      
        }
        return counter;    
      }

My code returns 4 for this problem but should return 8. Because I count just for the letters don't have any horizontally and vertically matches.

Upvotes: 3

Views: 2611

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Here's one way that runs a depth first search from each cell that hasn't been visited. I think this can also be solved with a flood fill, merging component labels when a connection is revealed.

function f(M){
  let m = M.length
  let n = M[0].length
  let visited = new Array(m)
  for (let i=0; i<m; i++)
    visited[i] = new Array(n).fill(0)
    
  function getNeighbours(y, x){
    let c = M[y][x]
    let neighbours = []

    if (y > 0 && !visited[y-1][x] && M[y-1][x] == c)
      neighbours.push([y-1, x])
    if (y < m - 1 && !visited[y+1][x] && M[y+1][x] == c)
      neighbours.push([y+1, x])
    if (x > 0 && !visited[y][x-1] && M[y][x-1] == c)
      neighbours.push([y, x-1])
    if (x < n - 1 && !visited[y][x+1] && M[y][x+1] == c)
      neighbours.push([y, x+1])

    return neighbours
  }
    
  function dfs(y, x){
    let stack = [[y, x]]
  
    while (stack.length){
      let [y, x] = stack.pop()
      visited[y][x] = 1
      stack.push(...getNeighbours(y, x))
    }
  }
  
  let count = 0
  
  for (let i=0; i<m; i++){
    for (let j=0; j<n; j++){
      if (!visited[i][j]){
        count++
        dfs(i, j)
      }
    }
  }
  
  return count
}

var M = [
  "ababc",
  "abbba",
  "aaabb",
  "bcccb",
  "acbbb",
  "aaabb"
]

console.log(f(M))

Upvotes: 3

Related Questions