Java brute force + one optimization from loop


  • 0
    D

    Learned from https://discuss.leetcode.com/topic/71256/easy-understanding-java-solution-with-detailed-explanation-21ms. Basically we add a new s1, we try to match once, and we get some remaining string. Then we add another new s1, then we try to match again, then we get another remaining string. The key point is that the remaining string might repeat itself, hence a loop is formed. The loop is the key to speed up the brute force "adding a s1, match" process.

    public class Solution {
        public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
            if (s1 == null || s1.length() == 0 || n1 == 0 || s2 == null || s2.length() == 0 || n2 == 0
                    || impossibleMatch(s1, s2)) {
                return 0;
            }
            int matched = 0;
            int currentPos = 0;
            String lastRemain = "";
            Map<String, MatchReport> reports = new HashMap<>();
            while ((currentPos + lastRemain.length()) / s1.length() < n1) {
                if (reports.containsKey(lastRemain)) {
                    LoopReport loop = analyzeLoop(reports, lastRemain);
                    int loops = (s1.length() * n1 - currentPos) / loop.passedChars;
                    matched += loops * loop.matched;
                    currentPos += loops * loop.passedChars;
                    reports.clear();
                } else {
                    MatchReport report = match(lastRemain + s1, s2);
                    reports.put(lastRemain, report);
                    matched += report.matched;
                    currentPos += report.passedChars;
                    lastRemain = report.remain;
                }
            }
            return matched / n2;
        }
    
        private LoopReport analyzeLoop(Map<String, MatchReport> reports, String entrykey) {
            int looplen = 0;
            int matched = 0;
            String key = entrykey;
            do {
                MatchReport report = reports.get(key);
                looplen += report.passedChars;
                matched += report.matched;
                key = report.remain;
            } while (!key.equals(entrykey));
            return new LoopReport(matched, looplen);
        }
    
        private MatchReport match(String str1, String str2) {
            int p1 = 0;
            int p2 = 0;
            int matched = 0;
            int end = 0;
            while (p1 < str1.length()) {
                char ch1 = str1.charAt(p1);
                char ch2 = str2.charAt(p2);
                if (ch1 == ch2) {
                    if (++p2 == str2.length()) {
                        p2 = 0;
                        matched++;
                        end = p1 + 1;
                    }
                }
                p1++;
            }
            return new MatchReport(matched, str1.substring(end), end);
        }
    
        private boolean impossibleMatch(String str1, String str2) {
            Set<Character> chars = new HashSet<>();
            for (int i = 0; i < str2.length(); i++) {
                chars.add(str2.charAt(i));
            }
            for (int i = 0; i < str1.length(); i++) {
                chars.remove(str1.charAt(i));
            }
            return chars.size() > 0;
        }
    
        class MatchReport {
            int matched;
            String remain;
            int passedChars;
            MatchReport(int matched, String remain, int passedChars) {
                this.matched = matched;
                this.remain = remain;
                this.passedChars = passedChars;
            }
        }
    
        class LoopReport {
            int matched;
            int passedChars;
            LoopReport(int matched, int passedChars) {
                this.matched = matched;
                this.passedChars = passedChars;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.