What is the complexity of the code for finding a word in a set of cubes

Question

I decided the program here . I used to think that the complexity was O (n!) Where n are the characters in the word.

But today I feel that this is wrong. It should be (6) ^ (characters in the word), where 6 are sides in the cube.

Having made it more general, assuming that the cube has more than 6 sides, the complexity should be O (cubefaces ^ (characters in the input word))

Can someone explain to me the time complexity in this case?

Answer 1

If exists if (cubeMatrix.length != word.length()) return false; , and each side letter of the cube is unique (i.e. no two sides of the cube have the same letter), then the time complexity of your algorithm is O (S ^{N - S + 1} S!), When N> = S and O ( SN!), When N <= S. Here S is the number of sides of the cube, and N is the number of cubes.

In short, you make a recursive call only when there is an unused letter in the word corresponding to the letter on the side of the cube, so in the worst case, the number of times you make a recursive call is no more than the number of words with letters left unused. And the number of unused letters of the word decreases with increasing depth of recursion, and ultimately this number becomes less than the number of sides of the cube. Therefore, in the final recursive depths, complexity becomes a factorial.

A bit more

We introduce f (n) how many times you call findWordExists with cubeNumber = n. We also introduce g (n) how many times findWordExists with cubeNumber = n calls itself recursively (but now with cubeNumber = n + 1).

f (0) = 1 because you are calling findWordExists not recursively only once.

f (n) = f (n - 1) g (n - 1) for n> 0.

We know that g (n) = min {S, N - n}, because, as I have already pointed out, findWordExists called recursively no more than the number of letters left - if (frequency > 0) is responsible for this; and the number of remaining letters is equal to the number of remaining cubes, i.e. N - n.

Now we can calculate how many times findWordExists is called in total:
f (0) + f (1) + ... + f (N) =
= 1 + g (0) + g (0) g (1) + ... + g (0) g (1) ... g (N - 1) =
= 1 + S + S ² + ... + S ^{N - S} + S ^{N - S} (S - 1) + S <sup = N - S (S - 1) (S - 2) + ... + S ^{N - S} (S - 1) (S - 2) ... 1 =
= O (S ^{N - S} S!).

But each call to findWordExists (except for the finals) iterates on each side, so we need to multiply the number of calls to findWordExists by the number of sides: SO (S ^{N - S} S!) = O (S ^{N - S + 1} S!) - and this is our temporary complexity.

Best algorithm

Actually, your problem is the problem of two-way matching, so there are much more efficient algorithms than brute force, for example. Kuhns algorithm .

The complexity of the Kuhn algorithm is O (NM), where N is the number of vertices and M is the number of edges. In your case, N is the number of cubes, and M is just N ^2, so the complexity in your case can be O (N ³ ). But you also need to iterate over all sides of all cubes, so if the number of sides of the cube is greater than N ² then the complexity is O (NS), where S is the number of sides of the cube.

Here is a possible implementation:

 import java.util.*; public class CubeFind { private static boolean checkWord(char[][] cubes, String word) { if (word.length() != cubes.length) { return false; } List<Integer>[] cubeLetters = getCubeLetters(cubes, word); int countMatched = new BipartiteMatcher().match(cubeLetters, word.length()); return countMatched == word.length(); } private static List<Integer>[] getCubeLetters(char[][] cubes, String word) { int cubeCount = cubes.length; Set<Character>[] cubeLetterSet = new Set[cubeCount]; for (int i = 0; i < cubeCount; i++) { cubeLetterSet[i] = new HashSet<>(); for (int j = 0; j < cubes[i].length; j++) { cubeLetterSet[i].add(cubes[i][j]); } } List<Integer>[] cubeLetters = new List[cubeCount]; for (int i = 0; i < cubeCount; i++) { cubeLetters[i] = new ArrayList<>(); for (int j = 0; j < word.length(); j++) { if (cubeLetterSet[i].contains(word.charAt(j))) { cubeLetters[i].add(j); } } } return cubeLetters; } public static void main(String[] args) { char[][] m = {{'e', 'a', 'l'} , {'x', 'h' , 'y'}, {'p' , 'q', 'l'}, {'l', 'h', 'e'}}; System.out.println("Expected true, Actual: " + CubeFind.checkWord(m, "hell")); System.out.println("Expected true, Actual: " + CubeFind.checkWord(m, "help")); System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "hplp")); System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "hplp")); System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "helll")); System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "hel")); } } class BipartiteMatcher { private List<Integer>[] cubeLetters; private int[] letterCube; private boolean[] used; int match(List<Integer>[] cubeLetters, int letterCount) { this.cubeLetters = cubeLetters; int cubeCount = cubeLetters.length; int countMatched = 0; letterCube = new int[letterCount]; Arrays.fill(letterCube, -1); used = new boolean[cubeCount]; for (int u = 0; u < cubeCount; u++) { if (dfs(u)) { countMatched++; Arrays.fill(used, false); } } return countMatched; } boolean dfs(int u) { if (used[u]) { return false; } used[u] = true; for (int i = 0; i < cubeLetters[u].size(); i++) { int v = cubeLetters[u].get(i); if (letterCube[v] == -1 || dfs(letterCube[v])) { letterCube[v] = u; return true; } } return false; } } 

Answer 2

 for (int i = 0; i < cubeMatrix[cubeNumber].length; i++) 

This will tell you about the number of characters in the given cubes (or, rather, about the faces of the cube).

Also, inside this loop you have

 if (frequency > 0) { charFreq.put(cubeMatrix[cubeNumber][i], frequency - 1); if (findWordExists(cubeMatrix, charFreq, cubeNumber + 1)) { return true; .. // and so on. 

This will result in a recursive call, thereby calling for cubeNumber + 1, then cubeNumber + 1 + 1, .., etc.

And finally, when is this condition

 if (cubeNumber == cubeMatrix.length) { for (Integer frequency : charFreq.values()) { if (frequency > 0) return false; } return true; } 

will meet, for-loop will not be executed further.

Assuming no. cubes = n, and the symbols stored in each cube are the generalized faces of each cube (as invented by OP) = f.

ANALYSIS BASED ON EXAMPLES: -

Starting from the 0th cube to the (n-1) th cube, the for-loop will iterate for cubeMatrix [cubeNumber] .length times, which is equal to the number of characters stored in each cube = f times.

And in each iteration of the for loop, the actual recursive call in case of cubeNumber 0 will be n-1 times until it reaches the last cube number.

Therefore, for each character record in cubeArray (f characters), we must call all available cubes (total n according to our assumption).

Therefore, the total number of times the code checks for the presence of the word = f ^ n.

In your terms, f = cubefaces = the number of characters possible on the edges of your generalized cube;

and, n = the total number of cubes available for your test.

It depends on the frequency of characters, which are reduced based on the character in the word, when the word length does not match the number of cubes. In this case, the result will be false.

But in the case where the word length is equal to the number of cubes, in the worst case, the output signal does not depend on the word length.

Strictly, this will also depend on the number of characters of the word (since comparison with the frequency will reduce several cases in the calculation), but, unfortunately, in the worst case, it does not depend on the number of characters in the word , since we will check all the character records in all available cubes to create a word.