Revision 317e1405-a3d8-432e-9748-8c73b54dc3d4 - Code Golf Stack Exchange

#Java 10, <s>356</s> <s>342</s> <s>284</s> <s>275</s> 233 bytes

<!-- language-all: lang-java -->

 import java.util.*;k->r->{var S=new Stack();p(S,"",k);int c=0;for(var p:S)c+=(p+"").matches(r.replaceAll("\\{,(\\d+\\})","{0,1ドル"))?1:0;return c;}void p(List S,String p,int k){if(k<1)S.add(p);else for(char i=32;i<127;)p(S,p+i++,k-1);}

Works, but way too slow for \$n\geq4\$.

[Try it online.](https://tio.run/##fVTNcpswEL7nKXY0nYlkCWyZ/DQhtieHdtqZdHrgCBxkIccEDAzIaV3sax@gj9gXcQXBaYw7FTOwfLuf9mNXy5N4FtZTlOzjVZGXGp7Mu73WcWoPXBgOgfIb0DnopYL5RitL5utMn8lUVBV8EXFWn8EbzmKdSR3nmf2xM@4@Z1o9qpL9N8jTZZw9MuiCp1NYwAT2iTUtrWn9LErwJpn6Bp4WMsHELbDHEGIJceNMg5yM3EVe4iauuPWIpBNcUISIvRJaLlWFS7tURSqkuk9TjIKgZjgIIhoEO4IYqkfsHUeEzPjtyC2VXpcZSHfnPudxBAV@iCsNHnvRCAVrUiakjhc4uePEs0UU4YK4Kq0UNDLk0uiIJ87Yje/4@NoljdqCxpSyxOLE3e3dM1O0Yj1PYwmVFto82lwrU0/8kscPQZCmtgBaVRoje4DYiLg9hJ8g4xPEaZHh8C9ycRQj5rJPa6FjXgv1iVshtyI6YeP5VpIDethgqUzt822eG8/lsUfropqdoHnN2cUu3SB21Xc4rMW5c33kwXxEKGL/BN/3pAfBrP@Jvr4Ol37MQ7@6DCGuQPqjPIz8D8oJ4dHYX0M/5Q/hwmQ@zhEE1LnkcOPzsXMVgj@ybkIj0tl15piNO7O9vfIPcqx@JwOz@phPZ4PwAB4y388l9iPrRzjYYvsToaa4nJ90ad5vho27ayuIWdumOfmhA68JTc8jFdZG/IG/a07u2yPbRnajUZrZ/c6gm492I29TabWy87W2CxOj0wyfo3PaRlJkPhGyCaIJRfD75y9AtBny5q@Cib2wRVGkG5yQzmhJpJOx2/8B)

**Explanation:**

 import java.util.*; // Required import for Stack and List
 k->r->{ // Method with integer and String parameter and integer return-type
 var S=new Stack(); // Create a List
 p(S,"",k); // Put all permutations of length `k` consisting of printable ASCII
 // characters in this list
 int c=0; // Counter-integer, starting at 0
 for(var p:S) // Loop over all permutations
 c+= // Increase the count by:
 (p+"") // Convert the permutation from Object to String
 .matches(r // If it matches the input-regex,
 .replaceAll("\\{,(\\d+\\})","{0,1ドル"))?
 // after we've replaced all {,m} with {0,m}
 1 // Increase the counter by 1
 : // Else:
 0; // Leave the count the same by increasing with 0
 return c;} // And return the counter as result

 void p( // Separated method with three parameters and no return-type, where:
 List S, // `S` is the List to put every permutation-String in
 String p, // `p` is the prefix-String, starting empty
 int k){ // `k` is the length the permutations we want to generate
 if(k<1) // If `k` is 0:
 S.add(p); // Add the current prefix-String to List `S`
 else // Else:
 for(char i=32;i<127;)
 // Loop over the printable ASCII characters:
 p( // And do a recursive call, with:
 S,p+i++, // The prefix-String appended with the current character
 k-1);} // And `k` decreased by 1

Some notes:

- Java's regex only supports `{n,m}` and `{n,}`, since `{,m}` could be written as `{0,m}`.
- And Java's [`String#matches`](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/String.html#matches(java.lang.String)) builtin implicitly adds a leading `^` and trailing `$` to check the entire String.