[关闭]
@natsumi 2017-03-25T14:35:36.000000Z 字数 681 阅读 1089

偶串

Algorithms


题目

偶串定义:字符串中每种字符都出现偶数次
求给定字符串的所有子串(连续的x个字符组成)中有多少个偶串

暴力算法会超时 80%通过

  1. public class EvenString {
  2. public static int count(String str){
  3. if(str == null || str.length() <= 1)
  4. return 0;
  5. int count = 0;
  6. for(int i = 2; i <= str.length(); i += 2){
  7. for(int j = 0; j + i - 1 < str.length(); j++){
  8. if(isEven(str, j, j + i - 1)){
  9. count++;
  10. }
  11. }
  12. }
  13. return count;
  14. }
  15. private static boolean isEven(String str, int i, int j){
  16. int[] ch = new int[26];
  17. for(int k = i; k <= j; k++){
  18. ch[str.charAt(k) - 'a'] += 1;
  19. }
  20. for(int m = 0; m < 26; m++){
  21. if(ch[m] % 2 != 0)
  22. return false;
  23. }
  24. return true;
  25. }
  26. public static void main(String[] args) {
  27. // Main main = new Main();
  28. // Scanner sc = new Scanner(System.in);
  29. // while(sc.hasNextLine()){
  30. // String str = sc.nextLine();
  31. // System.out.println(count(str));
  32. // }
  33. System.out.println(count("abbc"));
  34. }
  35. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注