Question

programming language is JAVA:

We wish to implement a method  String insert(char c, String s) that returns a string with c inserted in the correct position in already sorted String s. To do so we will implement insert as follows:

static  String insert(char c, String s) {

return insertHelper(c, "", s);

}

static  String insertHelper(char c, String left, String right) {} // strip leading characters from right, & append to left 'till insertion point found. Now return left + c + right.

For example, insert('e', "bcdfg") would call

insertHelper('e', "", "bcdfg") which would recursively call

insertHelper('e', "b" , "cdfg") followed by

insertHelper('e', "bc" , "dfg") followed by

insertHelper('e', "bcd", "fg).

This last call would then return "bcd" + 'e' + "fg" which is gives the final result "bcdefg".

IMPLEMENT insertHelper. (Don't implement insert() )

Your implementation of insertHelper must be tailRecursive.

Answer 1

class SortedInsertion{    //main method    public static void main(String args[]){           System.out.println("insert(d,bdefg) = "+insert('d',"bdefg"));        System.out.println("insert(a,bdefg) = "+insert('a',"bdefg"));        System.out.println("insert(h,bdefg) = "+insert('h',"bdefg"));        System.out.println("insert(c,bdefg) = "+insert('c',"bdefg"));    }    //insert function    public static String insert(char c,String s){        return insertHelper(c,"",s);    }    //insertHelper function    public static String insertHelper(char c,String left,String right){        //base conditions        //if right string is null then we have to return left stirng        if(right.equals("")){            return left+c;        }        //if there is know left string               else if(left.equals("")){            //condtion to insert c at beggining of string            if(c<=right.charAt(0)){                return c+right;            }            else{                left=left+right.charAt(0); //adding first charecter of right string to left string end                right=right.substring(1,right.length()); //removing frist charecter of right string                return insertHelper(c,left,right);//tail recursive calling            }        }        //inserting c at porper position        else if(left.charAt(left.length()-1)<=c && c<=right.charAt(0)){                         return left+c+right;        }        else{            left=left+right.charAt(0); //adding first charecter of right string to left string end            right=right.substring(1,right.length());//removing frist charecter of right string            return insertHelper(c,left,right);//tail recursive calling        }    } }

C:\Windows system32\cmd.ex insert (d.bdefg bddefg insert(a,bdef g abdefg insert(h.bdef gbdefgh insert<c.bdefg> - bcdefg Press any key to continue - . -