[Java] O(N) Simple solution - compute the longest suffix of word2 for each index in word1
Intuition\nCalculate longestSuffix defined below:\n\n- longestSuffix[i] := the longest length of suffix of word2 exists in word1[i..]\n\nAnd use this to compute
# Intuition\nCalculate `longestSuffix` defined below:\n\n- longestSuffix[i] := the longest length of suffix of word2 exists in word1[i..]\n\nAnd use this to compute the result.\nSorry for short explanations, but please refer to the code for more detail.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int[] validSequence(String word1, String word2) {\n        int len1 = word1.length();\n        int len2 = word2.length();\n        // longestSuffix[i] := the longest length of suffix of word2 in word1[i..]\n        int[] longestSuffix = new int[len1 + 1];\n        int i2 = len2 - 1;\n        for (int i1 = len1 - 1; i1 >= 0; i1--) {\n            if (i2 >= 0 && word1.charAt(i1) == word2.charAt(i2)) {\n                longestSuffix[i1] = len2 - i2;\n                i2--;\n            } else {\n                longestSuffix[i1] = i1 < len1 - 1 ? longestSuffix[i1 + 1] : 0;\n            }\n        }\n        // Compute the result with longestSuffix\n        int[] result = new int[len2];\n        int matchedLen = 0;\n        boolean replaced = false;\n        for (int i1 = 0; i1 < len1; i1++) {\n            if (word1.charAt(i1) == word2.charAt(matchedLen)) {\n                result[matchedLen] = i1;\n                matchedLen++;\n            } else if (!replaced && longestSuffix[i1 + 1] >= len2 - matchedLen - 1) {\n                // the condition means there exists a solution by replacing words1[i1] \n                replaced = true;\n                result[matchedLen] = i1;\n                matchedLen++;\n            }\n            if (matchedLen == word2.length()) return result;\n        }\n        return new int[]{};\n    }\n}\n```
['Java']