fork download
copy 
  1. import static java.lang.Math.min;
  2.  
  3. public class ManageSubsequences {
  4. 	final int INF = 1000 * 1000 * 1000 + 5;
  5. 	public int minAdded(String S, String A, String B) {
  6. 		int[][] dp = new int[A.length()+1][B.length()+1];
  7. 		for(int i = 0; i <= A.length(); ++i)
  8. 			for(int j = 0; j <= B.length(); ++j)
  9. 				dp[i][j] = INF;
  10. 		dp[0][0] = 0;
  11. 		for(int ii = 0; ii <= S.length(); ++ii) {
  12. 			for(int i = 0; i < A.length(); ++i)
  13. 				for(int j = 0; j < B.length(); ++j) {
  14. 					int i2 = i + 1;
  15. 					int j2 = j + (A.charAt(i) == B.charAt(j) ? 1 : 0);
  16. 					dp[i2][j2] = min(dp[i2][j2], dp[i][j] + 1);
  17. 				}
  18. 			if(ii == S.length())
  19. 				break;
  20. 			char must = S.charAt(ii);
  21. 			for(int i = A.length(); i >= 0; --i)
  22. 				for(int j = B.length() - 1; j >= 0; --j) {
  23. 					int x = dp[i][j];
  24. 					dp[i][j] = INF;
  25. 					int i2 = i + (i < A.length() && must == A.charAt(i) ? 1 : 0);
  26. 					int j2 = j + (must == B.charAt(j) ? 1 : 0);
  27. 					dp[i2][j2] = min(dp[i2][j2], x);
  28. 				}
  29. 		}
  30. 		int best = INF;
  31. 		for(int i = 0; i < B.length(); ++i)
  32. 			best = min(best, dp[A.length()][i]);
  33. 		if(best == INF) best = -1;
  34. 		return best;
  35. 	}
  36. }
  37.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:3: error: class ManageSubsequences is public, should be declared in a file named ManageSubsequences.java
public class ManageSubsequences {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/C7GGpd
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!