Writing sequences program in Java using recursion

I've been tasked with a problem that finds all the subsequences for a string. For example, if the string is "bat" the subsequences returns [,b, ba, at, bt, t] Notice how it doesn't have all the permutations of the string since it has to go in order. The first string is an empty string and that's apparently requires by the instructions. Another example is the string "brat". The expected output for that would be [, a, at, b, ba, bat, br, bra, brat, brt, bt, r, ra, rat, rt, t] I've tried to write a program that would use recursion and give me the output but I've only gotten so far. I'm sure I understand recursion but I don't know how I would try to code this problem. This is what I have so far: import java.util.ArrayList; public class Sequences { public static ArrayList sequences(String s) { ArrayList list = new ArrayList(); return subsequences(s, list); } public static ArrayList sequences(String s, ArrayList list) { list.add(""); if (s.length() == 0) list.add(s); else { list.add(s); String temp = s.substring(0,1); String next = s.substring(1, s.length()); list.add(temp); sequences(next); } return list; } } I also wrote a tester really quickly so I can test the problem since a tester wasn't provided to us: public class tester { public static void main(String[] args) { System.out.println(Sequences.sequences("at")); } } The output I'm getting is [, a] when I should have gotten [,a, at, t] Any help would be welcome!
Remember that you can pass around the ArrayList and modify it. Otherwise you're making a new list at every level of recursion, which is what you're doing, in fact... If you pass it as a parameter you can then modify it. You don't really need to send it back because objects are passed in Java by reference, not by value (or maybe it's the other way around, but the point is that you get to work on the same object)...

以上就是Writing sequences program in Java using recursion的详细内容,更多请关注web前端其它相关文章!

赞(0) 打赏
未经允许不得转载:web前端首页 » JavaScript 答疑

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

前端开发相关广告投放 更专业 更精准