Is there a way to write an algorithm for the following example without terrible runtime ?
This algorithm should be able to match two strings however each value in the string has a weight. (0-1: 0 meaning non essential, 1 meaning essential) If the weight is not 1, then the chars do not have to match and therefore a mismatch can occur. This is easier to explain with an example.
Pattern:
public static void main (String []args){
Sample:
public static void main (List<String> command_line_vals) {
Weights:
- 1 for
public static void main ( - 0.5 for
String [] - 0.1 for
args - 1 for
) {
The goal is to have these two match successfully. If the arguments are closer to the pattern, then it is scored higher. In this example it would mean that String []vals would rank higher than the above sample.
This is different from needleman-wunsch because if the char has a rank of !=1 then it should not match at all.
I would use regex however this would not allow me to rank the ones that do match. Would using regex first(wildcards for all non 1 valued chars), then needleman-wunsch on those that match work?
Suggestions and brain storming is welcome.
Thank you for your time.