Monday, January 18, 2016

Indeed: reverse String except HTML entity

Reverse string except for HTML entities, i.e, A HTML entities must be treated as an entire word without reverse.

e.g. "1234€" => "€4321"
"1234&euro" => "orue&4321"

"1234€567" => "765€4321"

Understand the problem:
Since a HTML entity must start with "&" and end with ";"
This problem can be solved in a two-step approach.
Step 1: reverse non-html tokens, and store the result into a list. For the HTML entity, do not reverse but just store into the result. 
Step 2: construct the final result just concatenate the list in a reverse order.

Code (Java):
public class Solution {
    public String reverseHTML(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        
        List<String> tokens = new ArrayList<>();
        int i = 0;
        int j = 0;
        
        while (j < s.length()) {
            char c = s.charAt(j);
            // Case 1: if c != & 
            if (c != '&') {
                j++;
            } else {
                // step 1: reverse substring before &
                if (j != 0) {
                    String token = reverse(s, i, j - 1);
                    tokens.add(token);
                }
                
                // step 2: put the html entity into the tokens
                StringBuffer sb = new StringBuffer();
                while (j < s.length() && s.charAt(j) != ';') {
                    sb.append(s.charAt(j));
                    j++;
                }
                
                if (j < s.length()) {
                    sb.append(';');
                    tokens.add(sb.toString());
                    // step 3: update i
                    j++;
                    i = j;
                }
            }
        }
        
        // Reverse the trailing chars
        if (i < j) {
            String token = reverse(s, i, s.length() - 1);
            tokens.add(token);
        }
        
        // Step 2: concatenate the final result
        StringBuffer result = new StringBuffer();
        for (i = tokens.size() - 1; i >= 0; i--) {
            result.append(tokens.get(i));
        }
        
        return result.toString();
    }
    
    private String reverse(String s, int start, int end) {
        StringBuffer sb = new StringBuffer();
        
        while (start <= end) {
            sb.append(s.charAt(end));
            end--;
        }
        
        return sb.toString();
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        
        //String s = "1234&euro;567";
        String s = "&euro4321";
        String result = sol.reverseHTML(s);
        
        System.out.println(result);
    }
}


2 comments:

  1. what should be the output of "51&23&123;097;6"

    ReplyDelete
    Replies
    1. it should be "6;7;90&123;32&15". Only consider the most inside entity.

      Delete