LensKart OA


This was one of the questions I got for Lenskart OA. Can someone help me understand how to solve this.
For the given sample input
a ={a}
b = {c,e}
h = {a, c}
So the combinations were
aa, bc, be, ha, hc
Answer: 5

My apprach::

mod = pow(10, 9) + 7

from collections import defaultdict

count = 0

def helper(arr, sub, n, m):
    global count
    if len(sub) == n:
        count = (count%mod) + 1
        return
    for i in range(0, len(arr)):
        if not sub or arr[i] in m[sub[-1]]: 
            helper(arr, sub+[arr[i]], n, m)
    
        
def CountPossibleStrings (LanguageDevice, N):
    # Write your code here
    m = defaultdict(list)
    rows = len(LanguageDevice)
    cols = len(LanguageDevice[0])
    res = 0
    for r in range(rows):
        for c in range(cols):
            if LanguageDevice[r][c] == '1':
                m[chr(ord('a')+r)].append(chr((ord('a')+c)))
                
    for v in m.values():
        helper(v, [], N-1, m)
    return count

I was not able to pass the test cases and I kep getting max recurssion depth error :frowning:

同学做的

static int MOD = (int)1e9 + 7;

public static void main(String[] args) {
	char[][] chars = { { 'a', 'a' }, { 'b', 'c' }, { 'b', 'e' }, { 'h', 'a' }, { 'h', 'c'} };
	int n = 2;
	System.out.println(getNumOfStrs(chars, n));
}

private static int getNumOfStrs(char[][] chars, int n) {
	Map<Character, Set<Character>> map = new HashMap<>();
	for(char i = 'a'; i <= 'z';i++) {
		map.put(i, new HashSet<>());
	}
	for(char[] cs : chars) {
		map.get(cs[1]).add(cs[0]);
	}
	int[][] dp = new int[n][26];
	for(int i=0;i<n;i++) {
		for(int j=0;j<dp[0].length;j++) {
			if(i == 0) {
				dp[i][j] = 1;
				continue;
			}
			char cur = (char)(j + 'a');
			for(char prev : map.getOrDefault(cur, new HashSet<>())) {
				dp[i][j] = (dp[i][j] + dp[i-1][prev - 'a']) % MOD; 
			}
		}
	}
	int res = 0;
	for(int i=0;i<dp[0].length;i++)
		res = (res + dp[n-1][i]);
	return res;
}