این یک مشکل آسان با شرح است:
به شما دو رشته s و t داده می شود به طوری که هر کاراکتر حداکثر یک بار در s رخ می دهد و t جایگشتی از s است.
تفاوت جایگشت بین s و t به عنوان مجموع اختلاف مطلق بین شاخص وقوع هر کاراکتر در s و شاخص وقوع همان کاراکتر در t تعریف می شود.
اختلاف جایگشت بین s و t را برگردانید.
مثال 1:
ورودی: s = “abc”، t = “bac”
خروجی: 2
توضیح:
برای s = “abc” و t = “bac”، اختلاف جایگشت s و t برابر است با مجموع:
تفاوت مطلق بین شاخص وقوع “a” در s و شاخص وقوع “a” در t.
تفاوت مطلق بین شاخص وقوع «ب» در s و شاخص وقوع «ب» در t.
تفاوت مطلق بین شاخص وقوع “c” در s و شاخص وقوع “c” در t.
یعنی اختلاف جایگشت بین s و t برابر است با |0 – 1| + |1 – 0| + |2 – 2| = 2.
مثال 2:
ورودی: s = “abcde”، t = “edbac”
خروجی: 12
توضیح: اختلاف جایگشت بین s و t برابر است با |0 – 3| + |1 – 2| + |2 – 4| + |3 – 1| + |4 – 0| = 12.
محدودیت ها:
1 <= طول <= 26
هر کاراکتر حداکثر یک بار در s رخ می دهد.
t جایگشت s است.
s فقط از حروف کوچک انگلیسی تشکیل شده است.
کلمات زیبای زیادی برای توصیف کارهایی که باید انجام شود وجود دارد، اما وقتی یک مثال را می‌بینید، درک اینکه مشکل در تلاش برای انجام چه چیزی است را آسان‌تر می‌کند.
پس از محاسبه اختلاف جایگشت، یک کم بیان وجود دارد که باید انجام شود:
- تکرار رشته.
- بازیابی کاراکتر بر اساس شاخص.
- این شاخص کاراکتر را در رشته دوم پیدا کنید.
- کم کردن شاخص اول با شاخص دوم.
- قدر مطلق را از آن تفریق بگیرید و همه را در یک خروجی جمع کنید.
حالا بیایید آن فکر را به کد جاوا ترجمه کنیم:
class Solution {
public int findPermutationDifference(String s, String t) {
int output = 0;
for(int i=0; i
زمان اجرا: 1 میلی‌ثانیه، سریع‌تر از 100 درصد موارد ارسالی آنلاین جاوا.
میزان استفاده از حافظه: 42.67 مگابایت، کمتر از 57.64 درصد موارد ارسالی آنلاین جاوا.
این یک راه حل خوب است که از نظر عملکرد نیز بسیار خوب است. اگر می‌خواهیم ظریف‌تر باشیم و راه‌حل را با Stream دنبال کنیم، راه‌حل این خواهد بود:
class Solution {
public int findPermutationDifference(String s, String t) {
return IntStream.range(0, s.length())
.map(i -> findCharPermutationDifference(s,t,i))
.sum();
}
public int findCharPermutationDifference(final String s, final String t, final int i) {
final char c = s.charAt(i);
final int j = t.indexOf(c);
return Math.abs(i - j);
}
}
زمان اجرا: 5 میلی‌ثانیه، سریع‌تر از 2.31 درصد موارد ارسالی آنلاین جاوا.
میزان استفاده از حافظه: 43.02 مگابایت، کمتر از 23.05 درصد موارد ارسالی آنلاین جاوا.
از نظر عملکرد و حافظه آنقدرها خوب نیست، اما با این وجود شیک است.
–
همین! اگر مورد دیگری برای بحث وجود دارد، لطفاً نظر خود را بگذارید، اگر چیزی را از دست دادم، به من اطلاع دهید تا بتوانم مطابق با آن به‌روزرسانی کنم.
تا پست بعدی! 🙂
