为链表的子字符串开发替换方法 class

Question

我有模仿标准 Java String 和 StringBuilder classes 的 class LString。我在开始实施替换方法以将子字符串 "LString" 的字符替换为 "lStr" 中的字符时遇到问题。我的替换方法在我的代码底部。

如果 If start == end 给出了特殊情况，它会在 LString 中的给定位置插入 "lStr"。如果 start == end == this.length()，它会在这个 LString 的末尾追加 lStr。

public class LString {

    node front;
    int length;
    LString next;

    // create node class
    public class node {
        char data;
        node next;

        public node(char newData) {
            data = newData;
        }

        public node(char newData, node newNext) {
            data = newData;
            next = newNext;
        }
    }

    // LString constructor
    // constructs LString object representing empty list of chars
    public LString(){
        this.length = 0;
        this.front = null;
    }

    // Construct LString copy of original parameter
    public LString(String original){
        //assign first char to front
        node curr = this.front;
        this.length = original.length();
        // loop through
        for (int i = 0; i < original.length(); i++) {
            if (i==0) {
                front = new node(original.charAt(i), null);
                curr = front;
            }else{
                curr.next = new node(original.charAt(i), null);
                curr = curr.next;
            }
        }
    }

    // return length in this LString
    // can use in LString constructor
    public int length(){
        return this.length;
    }

    //create and return string with contents of LString
    public String toString(){
        // use string builder to meet time limit
        StringBuilder builder = new StringBuilder();
        if(front == null){
            return "";
        }else{
            node curr = front;
            while(curr != null){
                builder.append(curr.data);
                curr = curr.next;

            }
            return builder.toString();
        }
    }

    //compares string lists 0 if equal -1 if less, and 1 if greater
    public int compareTo(LString anotherLString){
        //save lowest length of strings
        int minLength;
        // get front spots
        node curr = this.front;
        node otherCurr = anotherLString.front;
        // get lengths
        int thisString = length();
        int otherString = anotherLString.length();
        // get shortest length of 2 strings
        if(thisString < otherString){
            minLength = thisString;
        }else {
            minLength = otherString;
        }
        //go through characters in each string and compare for lexicographic order
        int iterate = 0;
        while(iterate < minLength){
            char string1Char = curr.data;
            char string2Char = otherCurr.data;
            if  (string1Char != string2Char) {
                return string1Char - string2Char;
            }
            iterate++;
            curr = curr.next;
            otherCurr = otherCurr.next;
        }
        return thisString - otherString;
    }

    //Return true if LString represents the same list of characters as other
    @Override
    public boolean equals(Object other) {
        if (other == null || !(other instanceof LString))
            return false;
        else{
            // use compareTo to determine if strings are the same
            LString otherLString = (LString)other;
            if(compareTo(otherLString) == 0){
                return true;
            }else{
                return false;
            }
        }
    }

    //Return the char at the given index in this LString.
    public char charAt(int index){
        int length = this.length();
        // check for index out of bounds
        if(index < 0 || index >= length){
            throw new IndexOutOfBoundsException();
        }
        // returns char at index
        node curr = front;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr.data;
    }

    //Set the char at the given index in this LString to ch.
    public void setCharAt(int index, char ch){
        // check for index out of bounds
        int length = this.length();
        if(index < 0 || index >= length){
            throw new IndexOutOfBoundsException();
        }
        // replaces char at index
        node curr = front;
        for (int i = 0; i < index; i++){
            curr = curr.next;
        }
        curr.next = new node(curr.data,curr.next);
        curr.data = ch;
    }

    //Returns a new LString that is a sub-string of this LString.
    public LString substring(int start, int end) {
        LString newLString = new LString();
        // handle exceptions
        if (start < 0 || start > end) {
            throw new IndexOutOfBoundsException();
        } else if (end > this.length()) {
            throw new IndexOutOfBoundsException();
            //return null in special case (empty LString)
        } else if (start == end) {
            //&& end == this.length()
            return newLString;
        } else {
            node node = this.front;
            for (int i = 0; i < start; i++) {
                node = node.next;
                // insert substring
            }
            node copy = new node(node.data);
            newLString.front = copy;
            for (int i = start + 1; i < end; i++) {
                node = node.next;
                copy = copy.next = new node(node.data);
            }
            return newLString;
        }
    }

    // Replaces this characters in a sub-string of this LString with the characters in lStr.
    public LString  replace(int start, int end, LString lStr) {

        // handle exceptions
        if(start <0 || start >end) {
            throw new IndexOutOfBoundsException();
        } else if (end > this.length()) {
            throw new IndexOutOfBoundsException();
    }
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        return null;
} // end class
        /*
                // create new LString
        LString newLString = new LString();

        node node = this.front;
        // to copy
        node copy = new node(node.data);
        // for node to replace
        node replace = lStr.front;

        if (start == end) {
            LString newLStr = new LString();
            return newLStr;
        }
        if (start == end && start == this.length()) {
            LString newLStr = new LString();
            return newLStr;
        */

    }
/*
//append / prepend methods for linked list
    //append
    public void append(int data){
        if (front == null){
            front = new node(data);
            end = front;
        }
        else {
            end.next = new node(data);
            end = end.next;
        }
        length++;
    }

    //prepend
    public void prepend(int data){
        if (front == null){
            end = new node(data);
            front = end;
        }
        else {
            front = new node(data,front);
        }
        length++;
    }
*/

替换 returns 作为此 LString 的子字符串的新 LString 之前的方法。感谢您的帮助，谢谢。

Answer 1

如果你有追加和 subsequence/substring 方法，你可以这样做：

public LString replace(int start, int end, LString replacement){
   //Do exception checks for start/end values here

   LString replacedLs = new LString();
   replacedLs.append(substring(0, start));
   replacedLs.append(replacement);
   replacedLs.append(substring(end, this.length));
   return replacedLs;
}

Answer 2

asiew 的答案听起来不错（更简单更好更安全），但是我们可以通过编写插入和删除方法使事情复杂一点，然后替换看起来像这样：

1) 插入 2）删除 3) 获胜

每个方法的（可能）次优解决方案如下所示：

private int insert(LString s, int index ) {
    node 
            n1 = front,
            n2 = null;        
    for (int i = 0; i < index-1; i++) {
        n1 = n1.next;
    }
    n2 = n1.next;
    if (n2 == null) return -1;
    int inserted = 0;
    for (char c : s.toString().toCharArray()) {
        n1.next = new node(c);
        n1 = n1.next;
        inserted++;
    }
    n1.next = n2;
    return inserted;
  }


private int remove(int from, int to) {
    node n1 = front,n2 = null;
    for (int i = 0; i < to+1; i++) {
        if (i<from) {
            n1=n1.next;
        } else if (i==from) n2=n1.next;
        else n2=n2.next;
    }
    n1.next = n2;
    return -1; // or whatever
}

public LString  replace(int start, int end, LString lStr) {
    int inserted = insert(lStr,start);
    int removed = remove(inserted+start-1,inserted+end-1);
    return this;
}

当然我们应该到处检查 nulls 无效参数等等。

为链表的子字符串开发替换方法 class

developing a replace method for the substring of a linked list class

java

string

linked-list

sublist