京东笔试编程题，重叠子串和括弧

京东笔试，第一条关于重叠子串的题目 




	 public static void main(String[] args) {


	 Scanner in = new Scanner(System.in);


	 String s = in.next();


	 char[] str = s.toCharArray();


	  


	 int index = -1;


	 for (int i = 1; i < str.length; i++) {


	  boolean overlap = true;


	  for (int j = 0; i+j < str.length; j++) {


	   if (str[i+j] != str[j]) {


	    overlap = false;


	    break;


	   }


	  }


	   


	  if (overlap) {


	   index = i;


	   break;


	  }


	 }


	 String res = null;


	 if (index != -1) {


	  res = s + s.substring(str.length - index);


	 }


	 else {


	  res = s + s;


	 }


	 System.out.println(res);


	 }




第二道 关于括弧的题目








	public class Second { 


	  


	 public static void main(String[] args) {


	  Scanner in = new Scanner(System.in);


	  String line = in.nextLine();


	  HashMap<String, Integer> map = new HashMap<>();


	   


	  int time = findTime(line, map);


	  System.out.println(time);


	   


	 }


	  


	 public static int findTime(String line, HashMap<String, Integer> map) {


	  if (line.isEmpty()) {


	   return 1;


	  }


	   


	  if (map.containsKey(line)) {


	   return map.get(line);


	  }


	   


	  int res = 0;


	   


	  for (int i = 1; i < line.length(); i++) {


	   if (line.charAt(i) == ')') {


	    String left = null;


	    if (i == 1) {


	     left = line.substring(2);


	    }


	    else {


	     left = line.substring(1, i) + line.substring(i+1);


	    }


	     


	    if (isLegal(left)) {


	     res += findTime(left, map);


	    }


	   }


	  }


	   


	  map.put(line, res);


	  return res; 


	 }


	  


	 public static boolean isLegal(String str) {


	  int l = 0, r = 0;


	  for (int i = 0; i < str.length(); i++) {


	   if (str.charAt(i) == '(') {


	    l++;


	   }


	   else {


	    r++;


	   }


	    


	   if (r > l) {


	    return false; 


	   }


	  }


	   


	  return true; 


	 }


	}